Haskell:将非无限列表变成无限列表+惰性(euler 391)

Question

我编写了以下 Haskell 代码来生成一个列表，其中第 n 个元素是将 1..n 写为二进制数时 1 的数量(顺便说一下，它与 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'？

Answer 1

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 即可轻松修复。