在Haskell中zipWith fibonacci的时间复杂度

Question

在Haskell中，fibonacci函数的规范zipWith实现是：

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我很难分析这个时间的复杂性（纤维!! n）。试着把它写在纸上，起初我认为它是指数级的。那么O（n ^ 2），但我不知道它是如何发生线性的。

为什么我认为它是线性的：https://wiki.haskell.org/The_Fibonacci_sequence#Canonical_zipWith_implementation

另外，我写了另一个代码：

fibs :: [Integer]
fibs = inc (0,1) where inc (a,b) = a : inc (b,a+b)

我相信这显然是O（n）。但是在ghci中使用：set + s选项，我发现zipWith实现明显胜过我的。

注意：我知道添加第n和第（n-1）个斐波那契数需要O（n）时间。因此，在测试时，我做了基本情况，即前两个元素0：0。使用相同的假设提到时间复杂性。

如果我可以通过跟踪这些函数调用获得一些帮助，那将会很棒。我很想知道哪个函数被调用时可能会打印一些东西让我知道发生了什么。

我未成功的尝试：

zipWith' = trace ("Called zipWith") (zipWith)
add' a b = trace (show a ++ " + " ++ (show b)) (add a b)
fibs = trace ("Called fibs") (1 : 1 : zipWith (+) fibs (tail fibs))

这不起作用。这些陈述只打印一份。除了添加'哪个工作正常，令人惊讶。

我想知道这些函数的调用次数和次数。

Answer 1

我相信你的版本很慢，主要是因为你在没有优化的情况下运行它，所以你最终会构建一堆不必要的元组。部分手动优化（和更惯用）的版本将是

fibs = inc 0 1
  where
    inc a b = a : inc b (a+b)

让我们来看看经典：

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

内存中的初始表示看起来非常像。这是一个指向数字1的列表缺点和指向数字1的第二个列表缺点和代表zipWith (+) fibs (tail fibs)的thunk。当那个thunk被迫时会发生什么？那么zipWith需要检查它的两个列表参数。它这样做，并且，看到它们不是null，产生一个列表cons指向代表1+1的thunk和代表zipWith (+) fibs' (tail fibs')的thunk，其中fibs'是指向序列中第二个cons的指针。对于每个fibs论证或类似的事情，没有必要再次评估zipWith。