Generalizing Fibonacci-type sequences (performance)

fibonacci, haskell, performance, recursion

Solution

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)

Problem

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?

Original source