Числа Хэмминга в Хаскеле

Question

Мне нужно определить список чисел, единственными простыми множителями которых являются 2, 3 и 5, числа Хэмминга. (Т.е. числа в виде 2^i * 3^j * 5^k. Последовательность начинается с 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …)

Я могу сделать это с помощью factors функция или иным образом. factors ниже следует вернуть факторы своего аргумента. Я верю, что правильно это реализовал.

   factors :: Int -> [Int]
   factors n = [x | x <- [1..(div n 2) ++ n], mod n x == 0]

Я попытался составить список из 2 ^ i * 3 ^ j * 5 ^ k, используя списочные выражения, но застрял при написании охранника:

hamming :: [Int]
hamming = [n | n <- [1..], „where n is a member of helper“]

helper :: [Int]
helper = [2^i * 3^j * 5^k | i <- [0..], j <- [0..], k <- [0..]]

Answer 1

Я могу сделать это с помощью factors функция или иным образом.

Я рекомендую делать это иначе.

Один простой способ - реализовать функцию, получающую простую факторизацию числа, и тогда вы можете получить

isHamming :: Integer -> Bool
isHamming n = all (< 7) $ primeFactors n

который затем будет использован для фильтрации списка всех натуральных чисел:

hammingNumbers :: [Integer]
hammingNumbers = filter isHamming [1 .. ]

Другой способ, более эффективный, состоит в том, чтобы избежать делений и фильтрации и создать список только чисел Хэмминга.

Один простой способ - использовать тот факт, что число n является числом Хемминга тогда и только тогда, когда

• n == 1, или же
• n == 2*k, где k это число Хэмминга, или
• n == 3*k, где k это число Хэмминга, или
• n == 5*k, где k число Хэмминга

Затем вы можете создать список всех чисел Хэмминга как

hammingNumbers :: [Integer]
hammingNumbers = 1 : mergeUnique (map (2*) hammingNumbers)
                                 (mergeUnique (map (3*) hammingNumbers)
                                              (map (5*) hammingNumbers))

где mergeUnique объединяет два отсортированных списка вместе, удаляя дубликаты.

Это уже довольно эффективно, но его можно улучшить, избегая создания дубликатов с самого начала.

Answer 2

Обратите внимание, что hamming набор

{2^i*3^j*5^k | (i, j, k) ∈ T}

где

T = {(i, j, k) | i ∈ [0..], j ∈ [0..], k ∈ [0..]}

Но мы не можем использовать [(i, j, k) | i <- [0..], j <- [0..], k <- [0..]]. Потому что этот список начинается с бесконечно многих троек, таких как (0, 0, k),
Учитывая любой (i,j,k), elem (i,j,k) T должен вернуть True за конечное время.
Звучит знакомо? Вы можете вспомнить вопрос, который вы задавали ранее: haskell бесконечный список инкрементных пар

В этом вопросе Хаммар дал ответ для пар. Мы можем обобщить это на тройки.

triples = [(i,j,t-i-j)| t <- [0..], i <- [0..t], j <- [0..t-i]]
hamming = [2^i*3^j*5^k | (i,j,k) <- triples]