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

Question

Я хочу написать функцию Хемминга в Haskell, которая получает список в качестве ввода. У меня уже есть это:

    merge :: [Integer] -> [Integer] -> [Integer]
    merge (x:xs)(y:ys)
      | x == y    = x : merge xs ys
      | x <  y    = x : merge xs (y:ys)
      | otherwise = y : merge (x:xs) ys


hamming :: [Integer] 
hamming 
  = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))

Это было просто. Но теперь я хочу что-то вроде "Хэмминга [4,6,7,9]" в качестве входных данных. Фактическое значение равно 1, но теперь оно должно быть списком, а каждое число в списке находится в списке Хэмминга. И конечно 2х 3х и 5х в списке.

Я написал что-то вроде

"hamming (x:xs) = x : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))" просто чтобы проверить список, но это не работает.

Answer 1

Хотя это дубликат, я покажу вам, как вы могли бы прийти к решению. Который действительно появляется в дубликате; здесь мое внимание будет сосредоточено на путешествии, а не на пункте назначения. Ты пытался

hamming (x:xs)
    = 1 : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))

Что здесь происходит? Это функция? Список? Здесь все перемешано; это беспорядок. Вы хотите превратить определение списка в функцию, назвав ее hamming [2,3,5], сказать; но то, что должно идти в map выражения? Вызов функции, hamming [2,3,5], также?

Но это противоречило бы цели, так как мы явно используем один и тот же список здесь в нескольких отдельных местах, то есть в трех (или, возможно, в большем...) map s, каждый из которых поддерживает свой собственный указатель на разделяемую последовательность. И выполнение отдельных вызовов функций, даже если они эквивалентны, (скорее всего и почти наверняка) приведет к созданию трех отдельных, даже если они равны. И это не то, что нам нужно здесь (это на самом деле забавное упражнение; попробуйте его и посмотрите, насколько медленнее и потребляет память функция).

Итак, разделите ваши проблемы! Перепишите это сначала как (все еще недействительно)

hamming (x:xs) = h where
  h = 1 : merge (map (2*) h) (merge (map (3*) h) (map (5*) h))

Сейчас h это общий список, и у вас есть свобода делать свою функцию, hamming что бы вы ни хотели, т.е.

hamming :: [Integer] -> [Integer] 
hamming [2,3,5] = h where
   h = 1 : merge (map (2*) h) (merge (map (3*) h) (map (5*) h))
     = 1 : merge (map (2*) h) (merge (map (3*) h) (merge (map (5*) h) []))

то есть,

     = 1 : foldr merge [] [map (p*) h | p <- [2,3,5]]

так как

       g a (g b (g c (... (g n z) ...)))
     =
       foldr g z [a,b,c,...,n]

и вот оно, ваш ответ, вплоть до некоторого обыденного переименования параметров.

Не забудьте переименовать свой merge функционировать как union Так как "слияние" не должно пропускать дубликаты, вызывая слияние как таковое. И сохраняйте все ваши определения, начиная с одного и того же уровня отступа в файле.