这是计算斐波纳契数的一个简单函数:
fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)
在ghci我可以快速计算系列.事实上,一些实验表明,计算在近似线性的时间内运行.
ghci> last $ take 100000 fib
354224848179261915075 -- takes under a second
如果我将类型签名更改为多态:
fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)
然后算法变慢.事实上,它似乎现在以指数时间运行!
切换到多态类型签名是否意味着列表在每个阶段都被完全重新计算？如果是这样,为什么？