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" -}
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 classical2, 3, 5
Hamming numbers, you obtain 6 as2 * 3
as well as3 * 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.
You can obtain the length of a list using the
length
function that is available from thePrelude
, but let me warn you right now that callinglength
should only be done if the length is really required, sincelength
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,
You could also use a guard with a
length
checkto make sure that your input list has exactly three elements, but you will regret that if you call
hamming 10 [1 .. ]
.