Search code examples
haskellfunctional-programmingfold

Build sorted infinite list of infinite lists

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!

Solution

  • 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?