Generalizing Fibonacci-type sequences (performance)

Question

Today I found the Haskell Fibonacci definition of:

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

Exploring, I wrote the "tribonacci" numbers as:

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

This works fine, so I tried to generalize to any "fibonacci-type" sequence using the same basic idea:

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

This works, too: it correctly gives the sequences I'm after. Unfortunately it's also horribly slow, many times slower even when generating the same fibonacci and tribonacci sequences. How can I express the same idea in a way that gets better performance?

Answer 1

You can use the worker-wrapper transform:

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)