推广Fibonacci型序列(性能)

Question

今天我发现了Haskell Fibonacci的定义:

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))

这也有效:它正确地给出了我所追求的序列.不幸的是,即使生成相同的斐波那契和三角洲序列,它也非常缓慢,慢很多倍.如何以更好的性能表达相同的想法？

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)