Haskell's linear recursion relation implementation is too slow

Question

I implemented a code that generates an infinite sequence defined by the base case and linear recurrence ratio coefficients.

import Data.List
linearRecurrence coef base | n /= (length base) = []
                           | otherwise = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
  where a     = linearRecurrence coef base
        n     = (length coef)

Here is the implementation of Fibonacci numbers. fibs = 0: 1: (zipWith (+) fibs (tail fibers))

Easy to see that

linearRecurrence [1,1] [0,1] = fibs

However, the calculation time fibs!!2000is 0.001 s and about 1 s for (linearRecurrence [1,1] [0,1])!!2000. Where does the huge speed difference come from? I made some of the functions strict. For example, it (sum . (zipWith (*) coef))is replaced by (id $! (sum . (zipWith (*) coef))), and this did not help.

Answer 1

You are reusing linearRecurrence coef base. Use sharing, for example:

linearRecurrence coef base | n /= (length base) = []
                           | otherwise = a
  where a = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
        n = (length coef)

a.

:

*Main> :set +s
*Main> fibs!!2000
422469...
(0.02 secs, 2203424 bytes)
*Main> (linearRecurrence [1,1] [0,1])!!2000
422469...
(0.02 secs, 5879684 bytes)