Хаскелл Хемминга, работает, но показывает дубликаты

Question

Я пытаюсь сгенерировать числа Хэмминга в haskell, проблема в том, что я получаю дубликаты # в моем списке вывода, и я не могу понять, почему именно. Должен ли я просто создать функцию удаления дубликатов или мне просто не хватает чего-то простого?

Также в функции Хемминга я хотел бы убедиться, что размер входного списка точно равен 3, как мне найти размер списка, чтобы я мог сделать сравнение?

{- 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" -}

Answer 1

Вы получаете дубликаты, потому что многие из чисел Хэмминга кратны нескольким из базовых чисел, и вы не удаляете дубликаты в своем merge функция. Например, для классического 2, 3, 5 Числа Хэмминга, вы получите 6 как 2 * 3 так же как 3 * 2,

Конечно, вы можете создать функцию удаления дубликатов. Поскольку созданный вами список отсортирован, это даже не будет очень неэффективным. Или вы можете удалить дубликаты в функции слияния.

Как мне найти размер списка, чтобы я мог сделать сравнение?

Вы можете получить длину списка, используя length функция, которая доступна из Prelude, но позвольте мне предупредить вас прямо сейчас, что зовет length должно быть сделано только если длина действительно требуется, так как length должен пройти весь список, чтобы рассчитать его длину. Если список оказывается длинным, это занимает много времени и может привести к огромному использованию памяти, если на этот список есть ссылки в другом месте, так что он не может быть собран мусором. Если список даже бесконечен, оценка его длины, конечно, никогда не закончится.

То, что вы хотите сделать, также может быть достигнуто путем сопоставления с шаблоном,

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

Вы также можете использовать охрану с length проверять

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

чтобы убедиться, что ваш входной список содержит ровно три элемента, но вы пожалеете, что если вы позвоните hamming 10 [1 .. ],

Answer 2

В List Модуль Haskell имеет дубликат для удаления nub, Вот это на hoogle: http://www.haskell.org/hoogle/?hoogle=nub. Это O(n^2), так что, возможно, вам лучше изменить merge, Но может быть стоит сначала использовать медленное решение, уже написанное для вас, прежде чем оптимизировать.

Я подозреваю, что вы пытаетесь изучить Haskell с помощью этого небольшого упражнения, но вот еще один способ записать числа Хемминга (без дубликатов, но не по порядку), используя монаду List:

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

Это делает ленивый, бесконечный список чисел Хэмминга. Вы можете эквивалентно написать это, используя понимание списка:

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