Please walk me through this "Erlang Programming" recursive sample

Question

From page 90 of Erlang Programming by Cesarini and Thomson, there is an example that has no detailed discussion. I'm quite the newbie to functional programming and recursive thinking, so I'm not familiar in solving problems this way.

"For example, the following function merges two lists (of the same length) by interleaving their values: "

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);
mergeL([],[],Zs) ->  Zs.

mergeR(Xs,[Y|Ys],Zs) ->  mergeL(Xs,Ys,[Y|Zs]);
mergeR([],[],Zs) ->  Zs.

How does this work? Thanks!

Answer 1

step through it

merge([1,2],[3,4])
reverse(mergeL([1,2],[3,4],[]))
reverse(mergeR([2],[3,4],[1]))
reverse(mergeL([2],[4],[3,1]))
reverse(mergeR([], [4], [2,3,1]))
reverse(mergeL([], [], [4,2,3,1]))
reverse([4,2,3,1])
[1,3,2,4]

It's always good to work these functions by hand on a piece of paper with a small input where you're trying to figure it. You'll quickly see how it works.

Answer 2

This function is called first:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

The empty list [] passed to mergeL is the accumulator - this is where the answer will come from. Note that the first function calls mergeL - the left merge.

Let us pretend that this function is called as so:

merge([1, 2, 3], [a, b, c])

Two lists of the same length. This first function then calls mergeL:

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);
mergeL([],[],Zs) ->  Zs.

There are 2 clauses in left merge. The call to mergeL with arguments will match these clauses in top down order.

The second of these clauses has three parameters - the first two of these are empty lists []. However the first time mergeL is called these two lists aren't empty they are the lists Xs and Ys so the first clause matches.

Lets break out the matches. This is the call to mergeL:

mergeL([1, 2, 3], [a, b, c], [])

and it matches the first clause in the following fashion:

X = 1
Xs = [2, 3]
Ys = [a, b, c]
Zs = []

This is because of the special form of the list:

[X | Xs]

This means match X to the head of the list (an individual item) and make Xs the tail of the list (a list).

We then build up the new function call. We can add the value X to the start of the list Zs the same way we pattern matched it out so we get the first mergeR call:

mergeR([2, 3], [a, b, c], [1])

The final argument is a one-item list caused by adding an item at the head of an empty list.

This this zips through until the end.

Actually the final clause of mergeL is redundant. By definition this function will exhaust in the final clause of mergeR (but I will leave that as an exercise for the reader).

Answer 3

What the example does is define a few states that the recursion will go through. There are 3 'functions' that are defined: merge, mergeL and mergeR.

The lists to merge are Xs and Ys, whereas the Zs are the result of the merge.

The merge will start with calling 'merge' and supplying two lists. The first step is to call mergeL with the two lists to merge, and an empty resultset.

[X|Xs] takes the first element of the list (very much like array_shift would). This element is added to the head of the resultset ([X|Zs] does this). This resultset (containing one element now) is then passed to the next call, mergeR. mergeR does the same thing, only it takes an element from the second list. This behaviour will continue as long as the lists fed to mergeL or mergeR are not empty.

When mergeL or mergeR is called with two empty lists ([]) and a resultset (Zs), it will return the resultset (and not do another run, thus stopping the recursion).

Summary:

The start of the recursion is the first line, which defines 'merge'. This start will set the whole thing in motion by calling the first mergeL.

The body of the recursion is lines 2 and 4, which define the behaviour or mergeL and mergeR, which both call each other.

The stop of the recursion is defined by lines 3 and 5, which basicly tell the whole thing what to do when there are no more elements in the array.

Hope this helps!

Answer 4

I always look for those functions that will terminate the recursion first, in this case:

mergeL([],[],Zs) ->  Zs.

and

mergeR([],[],Zs) ->  Zs.

both of those will basically finish the "merging" when the first two parameters are empty lists.

So then I look at the first call of the function:

merge(Xs,Ys) -> lists:reverse(mergeL(Xs,Ys,[])).

Ignoring the reverse for a second, you will see that the last parameter is an empty list. So I'd expect the various mergeL and mergeR functions to move the elements of that array into the final parameter - and when they are all moved the function will basically terminate (although finally calling the reverse function of course)

And that is exactly what the remaining functions do:

mergeL([X|Xs],Ys,Zs) ->  mergeR(Xs,Ys,[X|Zs]);

takes the first element of X and puts it into the Z array, and

mergeR(Xs,[Y|Ys],Zs) ->  mergeL(Xs,Ys,[Y|Zs]);

takes the first element of Y and puts it into the Z array. The calling of the mergeR from mergeL and vice versa is doing the interleave part.

What's interesting to see (and easy to fix) is that the arrays X and Y must be of the same length or you'll end up calling mergeL or mergeR with an empty array in X or Y - and that won't match either [ X | Xs] or [ Y | Ys].

And the reason for the reverse is simply around the relative efficiency of [ X | Zs] vs [ Zs | X]. The former is much more efficient.