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

Question

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

Now I need to combine them into one list, which orders integers. In addition, some integers can be displayed in several lists: in the output list, each integer can be displayed only 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'm a little stuck here. I do not know how to use foldr effectively to combine lists. I think I should compare the chapters of each list and make a new list out of it.

Answer 1

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

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

You will need to compare x and y and do something sensible, possibly related to the mergeSorted recursive call: this doesn't look so bad, does it?

Now suppose mergeSorted works, and you can turn two infinite sorted lists into one infinite sorted list. How do you turn N infinite sorted lists into one sorted list? Why, this is a simple fold! Just combine the two lists together, then merge the third with this, and the fourth with this, etc.

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

Answer 2

We can combine any pair of infinite monotonically increasing lists (for example, you) by repeatedly pulling the minimum element from one of the lists, unfoldr pull ( unfoldr is in Data.List ), with

 pull (x:xs,y:ys) | x<y = Just (x, (xs,y:ys)) | x>y = Just (y, (x:xs,ys)) | x==y = Just (x, (xs, ys)) -- pull same from both (NB!) 

and we can process any final list in pairs, halving its length:

 pairs f (x:y:t) = f (x,y) : pairs ft pairs _ t = t 

To repeat the step until the condition is met, the until task:

 uniquelyMerge xs = ... (until (...) (pairs (unfoldr pull)) xs) ..... 

Remember to process the empty list.