Oto prosta funkcja do obliczania liczb Fibonacciego:

fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)

W ghci mogę szybko obliczyć serię. W rzeczywistości trochę eksperymentów pokazuje, że obliczenia przebiegają w przybliżeniu liniowo.

ghci> last $ take 100000 fib
354224848179261915075         -- takes under a second

Jeśli zmienię podpis typu, aby był zamiast tego polimorficzny:

fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)

Następnie algorytm staje się wolniejszy. W rzeczywistości wygląda na to, że teraz działa w trybie wykładniczym!

Czy przejście na podpis typu polimorficznego oznacza, że ​​lista jest całkowicie przeliczana na każdym etapie? Jeśli tak, to dlaczego?