Hamming with lists in Haskell

Question

I want to write a hamming function in Haskell that gets a list as Input. I already have this:

    merge :: [Integer] -> [Integer] -> [Integer]
    merge (x:xs)(y:ys)
      | x == y    = x : merge xs ys
      | x <  y    = x : merge xs (y:ys)
      | otherwise = y : merge (x:xs) ys


hamming :: [Integer] 
hamming 
  = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))

That was easy. But now i want something like "hamming [4,6,7,9]" as input. The actual input is 1 but now the input should be a list and every number that is in the list is in the hamming-list. And of course 2x 3x and 5x are in the list.

I wrote something like

"hamming (x:xs) = x : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))" just to test with a list but it doesn't work.

Answer 1

Even though this is a duplicate, I'll show you how you could arrive at the solution. Which does appear at the duplicate; here my focus will be more on a journey, not its destination. You tried

hamming (x:xs)
    = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))

What is going on here? Is it a function? A list? It's all jumbled up here; it's a mess. You want to turn your list definition into a function, calling it as hamming [2,3,5], say; but then what should be going into the map expressions? A function call, hamming [2,3,5], as well?

But that would defeat the purpose, as we are expressly using the same list here in several separate places, i.e. the three (or possibly more...) maps, each maintaining its own pointer into the shared sequence. And making separate function calls, even if equivalent, will (most likely and nearly assuredly) produce three separate even if equal lists. And that is not what we need here (this is actually a fun exercise; try it and see how much slower and memory hungry the function will get).

So, separate your concerns! Re-write it first as (still invalid)

hamming (x:xs) = h where
  h = 1 : merge (map (2*) h) (merge (map (3*) h) (map (5*) h))

Now h is the shared list, and you have the freedom to make your function, hamming, whatever you want it to be, i.e.

hamming :: [Integer] -> [Integer] 
hamming [2,3,5] = h where
   h = 1 : merge (map (2*) h) (merge (map (3*) h) (map (5*) h))
     = 1 : merge (map (2*) h) (merge (map (3*) h) (merge (map (5*) h) []))

that is,

     = 1 : foldr merge [] [map (p*) h | p <- [2,3,5]]

because

       g a (g b (g c (... (g n z) ...)))
     =
       foldr g z [a,b,c,...,n]

and there it is, your answer, up to some mundane renaming of parameters.

Don't forget to rename your merge function as union, as "merge" isn't supposed to skip the duplicates, being evocative of mergesort as it is. And keep all your definitions starting at the same indentation level in the file.