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).