Haskell中的线性递归关系实现太慢了

Question

我已经实现了一个代码,该代码在给定基本情况和线性递归关系的系数的情况下生成无限序列.

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)

这是Fibonacci数的实现.fibs = 0:1 :( zipWith(+)fibs(tail fibs))

很容易看出来

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

但是计算的时间fibs!!2000是0.001 秒,大约是1 秒(linearRecurrence [1,1] [0,1])!!2000.速度的巨大差异来自哪里？我已经使一些功能严格.例如,(sum . (zipWith (*) coef))被替换为(id $! (sum . (zipWith (*) coef))),并没有帮助.

Answer 1

你linearRecurrence coef base反复计算.利用共享,如:

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)