Recursive Programming: Merge Lists (Mathematica: Join)

This example shows how to write a merge function in functional programming style using recursion. We take two Lists.

list1=RandomInteger[{1,10},5]
list2=RandomInteger[{-1,-10},7]

{3,10,2,10,3}
{-10,-9,-6,-2,-3,-8,-3}

As Maeder says about the ease and brevity of functional-style programming, it cannot get much simpler than this.

simplestMerge[a_List,b_List]:={a,b}//Flatten;
simplestMerge[list1,list2]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3}

To make it work on an unlimited number of Lists, we follow standard recursion procedure and define two base cases as the first piecewise definitions, then the general recursive function. The base cases will stop the recursion and let the nested recursion list unwind by evaluating from the base case 'outward.'

Use Clear liberally when construction piecewise definitions. To see how a recursive function works, use recursiveFunction//Trace with toy examples. Note that Flatten is a fast (Log@n) operation.

Clear@recursiveMerge;
recursiveMerge@a_List:=a;

recursiveMerge[a_List,b_]:={a,b}//Flatten;

recursiveMerge[a_List,b___List]:=recursiveMerge[a,recursiveMerge@{b}]//Flatten;

We must test it on use-cases.

list3=RandomInteger[{15,20},2]
list4=RandomInteger[{20,25},3]

{18,16}
{22,25,22}

recursiveMerge[list1,4]

{3,10,2,10,3,4}

recursiveMerge[list1,list2]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3}

recursiveMerge[list1,list2,list3]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3,18,16}

recursiveMerge[list1,list2,list3,list4]

{3,10,2,10,3,-10,-9,-6,-2,-3,-8,-3,18,16,22,25,22}

This post follows and expands Wagner Section 5.4.2, Recursion on lists. You cannot do better than these books. Since Wagner is out of print, I shall be posting excerpts to preserve his insights.

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}}

ApplyAll Applies a Function to all Subexpressions at Level One

ApplyAll

Instead of applying a function f to an entire expression, i.e. replacing the Head of the expression with f, use ApplyAll like Map to apply the function to each subexpression at level 1 of the expression. Apply defaults to Level 0 (the Head) and ApplyAll is just a convenient shorthand for Apply[ f, expr, 1].

Here is a typical example of ApplyAll. You have a List of number pairs and you want to perform some arithmetical operation such as add, multiply, divide, raise one to the power of the other, etc. (To remember the syntax of RandomReal I think of its arguments sequentially in English: "give me random reals between 1 and 20, 10 of them with length 2" (i.e. a 10 x 2 array).)

pairs=RandomReal[{0,1},{20,2}]

{{0.00994214,0.0701189},{0.024718,0.24013},{0.434799,0.996965},{0.323499,0.444366},{0.799502,0.843786},{0.964146,0.254526},{0.438815,0.943254},{0.228569,0.00348145},{0.247675,0.773157},{0.879202,0.615889},{0.898872,0.232664},{0.381568,0.75334},{0.464207,0.659948},{0.843115,0.179364},{0.287139,0.636774},{0.922514,0.193705},{0.969753,0.273868},{0.012059,0.247027},{0.560162,0.962637},{0.0593815,0.331142}}

Map doesn't work. It essentially disappears because it has no effect on a List:

Plus[List[a,b]]

{a,b}

Plus/@pairs

{{0.00994214,0.0701189},{0.024718,0.24013},{0.434799,0.996965},{0.323499,0.444366},{0.799502,0.843786},{0.964146,0.254526},{0.438815,0.943254},{0.228569,0.00348145},{0.247675,0.773157},{0.879202,0.615889},{0.898872,0.232664},{0.381568,0.75334},{0.464207,0.659948},{0.843115,0.179364},{0.287139,0.636774},{0.922514,0.193705},{0.969753,0.273868},{0.012059,0.247027},{0.560162,0.962637},{0.0593815,0.331142}}

But ApplyAll works perfectly; we always use its abbreviated version:

Plus@@@pairs

{0.080061,0.264848,1.43176,0.767865,1.64329,1.21867,1.38207,0.23205,1.02083,1.49509,1.13154,1.13491,1.12416,1.02248,0.923913,1.11622,1.24362,0.259086,1.5228,0.390524}

Times@@@pairs

{0.000697132,0.00593553,0.43348,0.143752,0.674608,0.2454,0.413914,0.000795751,0.191491,0.541491,0.209135,0.287451,0.306352,0.151224,0.182842,0.178696,0.265585,0.00297889,0.539232,0.0196637}

Here is a another example of ApplyAll. I want to make a toy directed graph so I can explore the new graph functions that have superseded the Combinatorica package as of Version 8.

randomEdges=RandomInteger[{1,20},{10,2}]

{{16,5},{17,17},{10,10},{15,2},{9,8},{20,9},{19,7},{20,15},{8,20},{11,3}}

Now I want to convert the pairs of numbers into a directed graph with DirectedEdge. My first try fails, again because each subexpression is a List.

toyGraph=DirectedEdge/@randomEdges

{DirectedEdge[{16,5}],DirectedEdge[{17,17}],DirectedEdge[{10,10}],DirectedEdge[{15,2}],DirectedEdge[{9,8}],DirectedEdge[{20,9}],DirectedEdge[{19,7}],DirectedEdge[{20,15}],DirectedEdge[{8,20}],DirectedEdge[{11,3}]}

What I need is ApplyAll.

toyGraph=DirectedEdge@@@randomEdges

It is equivalent to Apply[ DirectedEdge, randomEdges, 1].

Apply[DirectedEdge,randomEdges,1]