1

我想在 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))

那很简单。但现在我想要像“hamming [4,6,7,9]”这样的输入。实际输入是 1，但现在输入应该是一个列表，并且列表中的每个数字都在汉明列表中。当然 2x 3x 和 5x 在列表中。

我写了类似的东西

"hamming (x:xs) = x : merge (map (2*) hamming) (merge (map (3*) hamming) (map (5*) hamming))"只是为了测试一个列表，但它不起作用。

4

1 回答 1

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，每个都维护自己的指向共享序列的指针。并且进行单独的函数调用，即使是等效的，也会（很可能并且几乎可以肯定地）产生三个单独的即使相等的列表。这不是我们在这里需要的（这实际上是一个有趣的练习；尝试一下，看看这个函数会变得多慢和多消耗内存）。

所以，把你的顾虑分开！先重写为（仍然无效）

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，因为“合并”不应该跳过重复项，因为它会让人想起合并排序。并保持所有定义从文件中相同的缩进级别开始。

于 2017-11-29T15:07:41.860 回答