Номера Хэмминга в Haskell

Question

Мне нужно определить список чисел, единственными основными факторами которых являются 2, 3 и 5, номера Хэмминга. (Ie числа в виде 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^я * 3^J * 5^к, используя списочные, но застрял на написание охраннику:

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 сливает два отсортированных списков вместе, удаление дубликатов.

Это уже довольно эффективно, но it can be improved by avoiding producing duplicates from the beginning.

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 infinite list of incrementing pairs

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

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]