3

我编写了以下 Haskell 代码来生成一个列表，其中第 n 个元素是 1 的个数，将 1..n 写为二进制数（顺便说一下，它与 euler 391 有关）：

buildList :: a -> (a -> a) -> [a]
buildList start f = start : buildList (f start) f

differences :: [[Int]]
differences = buildList [0] (\x -> x ++ map (+1) x)

sequenceK' :: Int -> [Int]
sequenceK' n = tail $ scanl (+) 0 (last $ take n differences)

这导致sequenceK' n给出 2^(n-1) 个元素的列表。

这个问题有两个部分：

a) 为什么计算所需的时间head $ sequenceK' n会随着 n 的增加而增加？- 由于 ghc 的懒惰，我希望时间或多或少保持不变。

b）是否可以定义此列表的无限版本，以便我可以做类似的事情take而takeWhile不必担心传递给的参数的值sequenceK'？

4

1 回答 1

5

a) 因为你在打电话last $ take n differences，它必须做更多的工作，越大越好n。

b) 是的，这是可能的。最少思考的解决方案是只取我们在每个特定深度看到的最早元素：

*Main> take 20 . map head . transpose $ differences
[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3]

更好的解决方案是只生成有意义的位。我们可以通过观察以下等式来做到这一点：

differences' = 1 : (differences' >>= \x -> [x, x+1])

实际上，这有点偏离，您可能会猜到：

*Main> take 20 differences'
[1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3]

但是只要0在前面加上一个就可以很容易地修复它。

于 2012-09-04T01:32:53.453 回答