Merging Lists

The next problem is to write code that will merge two lists by creating a new list that shows alternate elements from your two source lists.

The spec doesn't say what to do if the lists are not the same length. We could imagine the case where the merged list has to show members of alternate lists and so it has to stop if either of the lists stops.

Or we could have the case of a process that is handling elements from two sources in a balanced way, so if one list comes to the end it is free to continue just with the other one.

So let's do it both ways.  Starting with three lists, two the same length and one longer:-

>>> stooges = ["Curly", "Larry", "Moe"]
>>> marxes = ["Groucho", "Harpo", "Chico"]
>>> dwarfs = ["Grumpy", "Dopey", "Happy", "Larry", "Linus", "Charlie", "Bob"]

Now for the case where the merged list stops if either list has stopped - so if we get to the end of xs or ys we return the empty list: otherwise create a new list of the first two elements of the source lists and concatenate this onto the rest of the result from the recursion:-

>>> def merge_lists_1(xs, ys):
if xs == [] or ys == []:
    return []
else:
    return [xs[0], ys[0]] + merge_lists_1(xs[1:], ys[1:])

No horses were scared in the creation of that function.  Does it work?

>>> merge_lists_1(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And it stops when the shorter list stops:-

>>> merge_lists_1(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy']

Now for the other case.  If one list comes to the end then return the other list; otherwise get two elements and join to the recursion as before:

>>> def merge_lists_2(xs, ys):
if xs == []:
    return ys
elif ys == []:
    return xs
else:
    return [xs[0], ys[0]] + merge_lists_2(xs[1:], ys[1:])

Now for lists of the same length:-

>>> merge_lists_2(stooges, marxes)
['Curly', 'Groucho', 'Larry', 'Harpo', 'Moe', 'Chico']

And if one list is longer then we finish off the longer list:-

>>> merge_lists_2(stooges, dwarfs)
['Curly', 'Grumpy', 'Larry', 'Dopey', 'Moe', 'Happy', 'Larry', 'Linus', 'Charlie', 'Bob']
>>>