Build sorted infinite list of infinite lists-CodePudding

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!

CodePudding user response：

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?

CodePudding user response：

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