1

我试图在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" -}
4

2 回答 2

2

您会得到重复项，因为许多汉明数是多个基数的倍数，并且您不会在merge函数中删除重复项。例如，对于经典的2, 3, 5汉明数，您可以得到 62 * 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 .. ].

于 2012-07-27T19:51:37.537 回答
1

在List模块中，Haskell 有一个名为nub. 这是在 hoogle 上：http ://www.haskell.org/hoogle/?hoogle=nub 。这是 O(n^2) ，所以你最好改变merge. 但是在优化之前首先使用已经为您编写的慢速解决方案可能是值得的。

我怀疑您正在尝试通过这个小练习来学习 Haskell，但这是使用List monad写出汉明数（没有重复，但不是按顺序）的另一种方法：

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]]
于 2012-07-28T03:27:24.843 回答