Haskell Hamming numbers, works but shows duplicates

Question

I am trying to generate hamming numbers in haskell, the problem is I get duplicate #'s in my output list and I cannot figure out why exactly. Should I just create a remove duplicates function or am I just missing something simple?

Also in the function hamming I would like to make sure the size of the input list is exactly 3, how do I find the size of a list so I can do the comparison?

{- Merge lists x&y of possibly infinite lengths -}
merge [] [] = []
merge [] ys = ys
merge xs [] = xs
merge xs ys = min x y : if x < y then merge (tail xs) ys
                             else merge xs (tail ys)
    where x = head xs
          y = head ys

{- multiply each element in y by x -}
times x [] = []
times x y = x * (head y) : times x (tail y)

{- find the hamming numbers of the input primes list -}
ham [] = []
ham x = 1 : merge (times (head x) (ham x))
             (merge (times (x !! 1) (ham x)) (times (last x) (ham x)))

{- returns x hamming #'s based on y primes of size 3 -}
hamming x [] = []
hamming x y = take x (ham y) 
{- hamming x y = if "y.size = 3" then take x (ham y) 
                                 else "Must supply 3 primes in input list" -}

coincidentally, `nodups xs = map head (Data.List.group xs)` for ordered non-decreasing lists. — Will Ness, Jul 27 '12 at 23:37

score 2 · Answer 1 · answered Jul 27 '12 at 19:51

You get duplicates because many of the hamming numbers are multiples of several of the base numbers, and you don't remove duplicates in your merge function. For example, for the classical 2, 3, 5 Hamming numbers, you obtain 6 as 2 * 3 as well as 3 * 2.

You could of course create a duplicate removal function. Since the list you create is sorted, that wouldn't even be very inefficient. Or you could remove the duplicates in the merge function.

how do I find the size of a list so I can do the comparison?

You can obtain the length of a list using the length function that is available from the Prelude, but let me warn you right now that calling length should only be done if the length is really required, since length has to traverse the entire list to calculate its length. If the list happens to be long, that takes a lot of time, and may cause huge memory usage if the list is referenced elsewhere so that it cannot be garbage-collected. If the list is even infinite, evaluating its length will of course never terminate.

What you want to do can also be achieved by pattern-matching,

ham [a, b, c] = list
  where
    list = 1 : merge (map (a*) list) (merge (map (b*) list) (map (c*) list))
ham _ = []

You could also use a guard with a length check

hamming x y
    | length y == 3 = take x (ham y)
    | otherwise     = []

to make sure that your input list has exactly three elements, but you will regret that if you call hamming 10 [1 .. ].

score 1 · Answer 2 · edited Jul 28 '12 at 16:10

In the List module, Haskell has a duplicate remover called nub. Here it is on hoogle: http://www.haskell.org/hoogle/?hoogle=nub. This is O(n^2) though, so you might be better off changing merge. But it may be worthwhile to first use a slow solution already written for you, before optimizing.

I suspect that you are trying to learn Haskell with this little exercise, but here's another way to write out the hamming numbers (no duplicates, but not in order) using the List monad:

uglyNumbers = do { n <- [0..] 
                 ; k <- [0..n] 
                 ; j <- [0..n-k] 
                 ; return $ (2^(n-k-j))*(3^j)*(5^k) }

This makes a lazy, infinite list of hamming numbers. You can equivalently write this using a list comprehension:

uglyNumbers' = [(2^(n-k-j))*(3^j)*(5^k) | n <- [0..], k <- [0..n], j <- [0..n-k]]

Haskell Hamming numbers, works but shows duplicates

2 Answers2