Recursive Programming on Lists (Arrays): Map

Here is a simple recursive mapping function. This is a recursion on Lists (arrays) with arbitrary argument types, not numbers.

Recall that Map is a classic functional-style, 'structural' command since it leads us to think in terms of applying a function to an entire structure, such as an array (a List in Mathematica). The Map function saves us the trouble of 'deconstructing' the array with a Do or For loop as in procedural programming.

We define a base case and a recursive case:

1. Base case: If the source List is empty, just return it

2. Recursive case: Call itself on the Rest of each successively smaller sub-List

Clear@recursiveMap;
recursiveMap[function_,aList_List]:=
If[aList=={},{},
Prepend[recursiveMap[function,Rest@aList],function@First@aList]]

We test the base case:

recursiveMap[f,{}]

{}

We test some recursive cases:

recursiveMap[f,{a,b,c}]

{f[a],f[b],f[c]}

recursiveMap[f,Range@5]

{f[1],f[2],f[3],f[4],f[5]}

How does it work? You can go through the Trace, but essentially by calling itself repeatedly on the Rest of list (via the first, recursive 'clause' of recursiveMap, recursiveMap[function,Rest@list]), it constructs successively smaller sub-Lists and eventually hits the empty List, which is the base case. 

Then it begins 'unwinding' and Prepend and the second clause of recursiveMap is repeatedly invoked (function@First@list). Starting with the last List of a single element (c in this Trace), it applies the function f to the First element of each sub-List and Prepends it to a growing List of results until the First element of the entire list is Prepended.

Trace@recursiveMap[f,{a,b,c}]

{recursiveMap[f,{a,b,c}],If[{a,b,c}=={},{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],{{a,b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]],{{Rest[{a,b,c}],{b,c}},recursiveMap[f,{b,c}],If[{b,c}=={},{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],{{b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]],{{Rest[{b,c}],{c}},recursiveMap[f,{c}],If[{c}=={},{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],{{c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]],{{Rest[{c}],{}},recursiveMap[f,{}],If[{}=={},{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{{}=={},True},If[True,{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{}},{{First[{c}],c},f[c]},Prepend[{},f[c]],{f[c]}},{{First[{b,c}],b},f[b]},Prepend[{f[c]},f[b]],{f[b],f[c]}},{{First[{a,b,c}],a},f[a]},Prepend[{f[b],f[c]},f[a]],{f[a],f[b],f[c]}}

Source: David Wagner

Ways to Create Arrays

Programmers often have to create an array. Of course, in Mathematica, you don't have to allocate memory for an array or dimension it or any of that outdated nonsense. Here are the six standard functions and common methods used to create arrays in Mathematica. Use the easiest-to-implement and most readable method for your application.

First there is the versatile function Array that applies a function to the array indices of any desired array dimension.

Array[g,{2,3}]

{{g[1,1],g[1,2],g[1,3]},{g[2,1],g[2,2],g[2,3]}}

To simply create a nested List of Integers you can use List as the function to apply to the array. "Give me 5 rows of 3 elements each:"

dataset=Array[List,{5,3}]

{{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}},{{3,1},{3,2},{3,3}},{{4,1},{4,2},{4,3}},{{5,1},{5,2},{5,3}}}

It is quite easy to create a similar array with one of the most versatile and commonly-used functions in functional programming, Table. It pays handsomely to become a power user of Table.

Table[{i,j},{i,5},{j,3}]

{{{1,1},{1,2},{1,3}},{{2,1},{2,2},{2,3}},{{3,1},{3,2},{3,3}},{{4,1},{4,2},{4,3}},{{5,1},{5,2},{5,3}}}

Table is highly versatile and can certainly be used to do many things. In some cases there is a built-in function that is more specialized. For instance, Table can be used to create a constant array. "Give me 25 7s:"

Table[7,{25}]

{7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7}

ConstantArray is a specialized function that does the same thing, but except for a little bit of clarity in reading the code doesn't do more than Table.

ConstantArray[7,25]

{7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7}

Table can generate random numbers using any of the random function family:

Table[RandomInteger[],{10}]

{1,1,1,0,0,0,0,1,1,1}

But for simple as well as higher-dimension arrays, the several half-dozen built-in random functions are superior and more readable than doing the same thing in Table.

RandomInteger[{1,5},{2,3}]

{{2,4,3},{2,1,3}}

Likewise, while Table can easily create a range of numbers, Range is superior.

Table[i,{i,7}]

{1,2,3,4,5,6,7}

Range@7

{1,2,3,4,5,6,7}

From 14 to 28 in steps of 2:

Range[14,28,2]

{14,16,18,20,22,24,26,28}

Those applications yield vectors, but here is a lesser-known usage of Range with a List as argument that generates an array. For each number in the List, Range yields a List of integers from 1 up to that number.

Range[{2,5,3}]

{{1,2},{1,2,3,4,5},{1,2,3}}

To more carefully control aspects of the array such as start, end, and step size, you may need to manually assemble the array with Table or Range.

{Range[14,28,2],Range[10^6,10^5,-2*10^5]}

{{14,16,18,20,22,24,26,28},{1000000,800000,600000,400000,200000}}

{Table[i,{i,14,28,2}],Table[j,{j,10^6,10^5,-2*10^5}]}

{{14,16,18,20,22,24,26,28},{1000000,800000,600000,400000,200000}}

Finally, MapIndexed is used in general to generate a List where a function is applied to a List of arguments along with an index number, which is the second argument.

MapIndexed[f,{a,b,c,d}]

{f[a,{1}],f[b,{2}],f[c,{3}],f[d,{4}]}

Using First strips off the enclosing List of the index.

MapIndexed[{#^2,First@#2}&,Range@5]

{{1,1},{4,2},{9,3},{16,4},{25,5}}