Warum beeinträchtigt das Hinzufügen einer polymorphen Typensignatur die Leistung?
Hier ist eine einfache Funktion zur Berechnung von Fibonacci-Zahlen:
fib :: [Int]
fib = 1 : 1 : zipWith (+) fib (tail fib)
In ghci kann ich die Serie schnell berechnen. Tatsächlich zeigt ein wenig experimentieren, dass die Berechnung in ungefähr linearer Zeit abläuft.
ghci> last $ take 100000 fib
354224848179261915075 -- takes under a second
Wenn ich stattdessen die Typensignatur in polymorph ändere:
fib :: Num a => [a]
fib = 1 : 1 : zipWith (+) fib (tail fib)
Dann wird der Algorithmus langsamer. Tatsächlich scheint es jetzt in exponentieller Zeit zu laufen!
Bedeutet das Umschalten auf eine polymorphe Typensignatur, dass die Liste in jeder Phase vollständig neu berechnet wird? Wenn ja warum?