How can I merge a finite number of infinite lists in Haskell?

Question

For an assignment I need to write some Haskell code which has as input a finite list consisting of infinite lists of integers, each list monotonically increasing.

Now, I need to merge these into one single list which orders the integers. Also, some integers may appear in multiple lists: in the output list, each integer may only appear once in the list.

So if the input is for example [ [1, 2, 6, 10, 28, 40, ...] [3, 4, 10, 28, 100, ...] , [any number of lists] ] then the output should be [1, 2, 3, 4, 6, 10, 28, 40, 100, ...]

I am a little stuck here. I do not know how to use foldr effectively to merge the lists. I think I should compare the heads of each list and make a new list out of that one.

Answer 1

You can simplify the problem a bit by thinking about merging two infinite sorted lists, and then try to generalize. The skeleton of that merge will look something like this:

mergeSorted :: Ord a => [a] -> [a] -> [a]
mergeSorted [] ys = ys
mergeSorted xs [] = xs
mergeSorted (x:xs) (y:ys) = ???

You'll have to compare x and y, and do something sensible, probably involving a recursive call to mergeSorted: this doesn't look too bad, right?

Now, let's imagine that mergeSorted works, and you can turn two infinite sorted lists into one infinite sorted list. How do you turn N infinite sorted lists into a single sorted list? Why, that's a simple fold! Just merge two lists together, then merge a third with that one, and a fourth with that one, and so on.

mergeAll :: Ord a => [[a]] -> [a]
mergeAll xss = foldr ???