Linear recurrence relation implementation in Haskell too slow

Question

I have implemented a code that generate the infinite sequence given the base case and the coefficients of a linear recurrence relation.

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 a implementation of Fibonacci numbers. fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

It's easy to see that

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

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

Did you use criterion to measure this? If not, do it to verify that your measurements aren't just a bad coincidence. — jmg
I just ran this through criterion (with -O2) on my netbook, and I get roughly a 10x difference between the two, not anything near the 1000x you claim to be seeing. — hammar

Stefan Holdermans Stefan Holdermans · Accepted Answer · 2011-11-30T09:27:53

You are computing linearRecurrence coef base repeatedly. Make use of sharing, as in:

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

Note the sharing of a.

Now you get:

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

Linear recurrence relation implementation in Haskell too slow

1 Answers