Build sorted infinite list of infinite lists

Question

I know it is impossible to sort infinite lists, but I am trying to write a definition of the infinite increasing list of multiples of n numbers.

I already have the function

multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]

that returns the infinite list of multiples of n. But now I want to build a function that given a list of Integers returns the increasing infinite list of the multiples of all the numbers in the list. So the function multiplesList :: [Integer] -> [Integer] given the input [3,5] should yield [3,5,6,9,10,12,15,18,20,....].

I'm new at Haskell, and I'm struggling with this. I think I should use foldr or map since I have to apply multiples to all the numbers in the input, but I don't know how. I can't achieve to mix all the lists into one.

I would really appreciate it if someone could help me.

Thank you!

You need to *merge* the lists. You can always merge two sorted lists, finite or not. Try merging two lists first. Then think of how an infinite number of lists could be merged and under what conditions. — n. m. could be an AI, Oct 14 '21 at 08:37
@n.1.8e9-where's-my-sharem. yes. I don't think it's necessary to merge infinitely many lists here, just finitely many infinite lists. — leftaroundabout, Oct 14 '21 at 08:38
BTW, that's almost the same merging operation that's the heart of mergesort. — leftaroundabout, Oct 14 '21 at 08:47
Use explicit recursion and define a function `merge` to merge two sorted lists. After that, you can use `merge` in a fold, and so define `multiplesList`. — chi, Oct 14 '21 at 09:32
I would use `filter` on the infinite list `[1..]` with a predicate that checks for divisibility by any of the numbers in the list of divisors. Provided that list is always finite this strikes me as easier than doing multiple maps and then merging. — Robin Zigmond, Oct 14 '21 at 11:42
@RobinZigmond, that sounds inefficient. Might be better to use a priority queue. — dfeuer, Oct 15 '21 at 09:10

score 2 · Accepted Answer · answered Oct 14 '21 at 11:00

You are in the right path. following the comments here is a template you can complete.


multiples :: Integer -> [Integer]
multiples n = map (*n) [1..]

-- This is plain old gold recursion.
mergeSortedList :: [Integer] -> [Integer] -> [Integer]
mergeSortedList [] xs = undefined
mergeSortedList xs [] = undefined
mergeSortedList (x:xs) (y:ys)
    | x < y  = x:mergeSortedList xs (y:ys) -- Just a hint ;)
    | x == y = undefined
    | x > y  = undefined

multiplesList :: [Integer] -> [Integer]
multiplesList ms = undefined -- Hint: foldX mergeSortedList initial xs
                             -- Which are initial and xs?
                             -- should you foldr or foldl?

Thank you! `multiplesList ms = foldr mergeSortedList [] (map multiples ms)` Solved it! — acampana, Oct 14 '21 at 11:05

Will Ness · Answer 2 · 2021-10-15T13:27:49.800

We can easily weave two infinite lists together positionally, taking one element from each list at each step,

weave (x:xs) ys = x : weave ys xs

or we could take longer prefixes each time,

-- warning: expository code only
weaveN n xs ys = take n xs ++ weaveN n ys (drop n xs)

but assuming both lists are not only infinite but also strictly increasing (i.e. there are no duplicates in the lists), we can guide the taking of prefixes by the head value of the opposite list:

umerge :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
umerge xs (y:ys) = a ++ [y | head b > y ] ++ umerge ys b
  where
    (a,b) = span (< y) xs

This is thus a possible encoding of the unique merge operation ("unique" meaning, there won't be any duplicates in its output).

Testing, it seems to work as intended:

> take 20 $ umerge [3,6..] [5,10..]
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]

> [3,6..42] ++ [5,10..42] & sort & nub
[3,5,6,9,10,12,15,18,20,21,24,25,27,30,33,35,36,39,40,42]

> [ p | let { ms :: [Integer] ; ms = takeWhile (< 25^2) $
          foldl1 umerge [[p*p,p*p+p..] | p <- [2..25]] },
    p <- [2..545],  not $ elem p ms ]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
 97,101,...........,499,503,509,521,523,541]

> length it
100

And with an ingenious little tweak (due to Richard Bird as seen in the JFP article by Melissa O'Neill) it can even be used to fold an infinite list of ascending lists, provided that it is sorted in ascending order of their head elements, so the head of the first argument is guaranteed to be the first in the output and can thus be produced without testing:

umerge1 :: Ord a => [a] -> [a] -> [a]
-- warning: only works with infinite lists
--          assumes x < y
umerge1 (x:xs) ~(y:ys) = x : a ++ [y | head b > y ] ++ umerge ys b
  where
    (a,b) = span (< y) xs

Now

> take 100 [ p | let { ms :: [Integer] ;
          ms = foldr1 umerge1 [[p*p,p*p+p..] | p <- [2..]] },
    p <- [2..],  not $ elem p $ takeWhile (<= p) ms ]

[2,3,5,7,11,13, ...... 523,541]

the same calculation works indefinitely.

_{to the literalists in the audience: yes, calling elem here is Very Bad Thing. The OP hopefully should have recognized this on their own, ^(*) but unfortunately I felt compelled to make this statement, thus inadvertently revealing this to them, depriving them of their would-be well-earned a-ha moment, unfortunately.}

_{Also, umerge1's definition can be radically simplified. Again, this is left to the OP to discover on their own. (which would, again, be much better for them if I wasn't compelled to make this remark revealing it to them --- finding something on your own is that much more powerful and fulfilling)}

_{^(*) and search for ways to replace it with something more efficient, on their own. No, this code is not presented as The Best Solution to Their Problem.}

Build sorted infinite list of infinite lists

2 Answers2