泛化斐波那契数列（性能）

Question

今天我找到了Haskell中斐波那契数列的定义：

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

在探索中，我将“tribonacci”数字写成了以下形式：

tribs = 0 : 0 : 1 : zipWith (+) (zipWith (+) tribs (tail tribs)) (drop 2 tribs)

这个方法很好用，所以我尝试使用相同的基本思路来概括任何“斐波那契类型”的序列：

nbonacci n   = (take n (repeat 0)) ++ [1] ++ (z n) 
   where z 1 = zipWith (+) (nbonacci n) (drop 1 (nbonacci n))
         z x = zipWith (+) (z (x-1)) (drop x (nbonacci n))

下面这种方法也可以：它能正确给出我想要的数列。不幸的是，这种方法速度非常慢，甚至比生成相同的斐波那契和Tribonacci数列时还要慢很多。有什么方法可以用更高的性能来表达相同的想法吗？

- Brian Fearn

Answer 1

您可以使用worker-wrapper转换技术：

nbonacci n = go where
    go = take n (repeat 0) ++ [1] ++ z n
    z 1 = zipWith (+) go (drop 1 go)
    z x = zipWith (+) (z (x-1)) (drop x go)

- Daniel Wagner

---

哇，谢谢！我不确定我完全理解为什么它有效，但我会阅读维基百科。 - Brian Fearn

@BrianFearn 这并不是真正的工作器包装转换。它所做的是给列表赋予一个名字 go，这个列表在所有相互调用的函数之间是共享的，避免了一直重新计算它的情况。你原来的代码中到处都有 nbonacci n，这是一个函数应用，这些结果默认情况下是不共享的。 - Ørjan Johansen