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)
سؤال
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?
المحلول
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)