Warum verschlechtert das Hinzufügen einer Signatur vom Typ "Polymorph" die Leistung? Fibonacci-Zahlen

Question

Hier ist eine einfache Funktion zu berechnen:

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

In GHCI ich schnell die Serie berechnen kann. 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 die Art Signatur zu ändern, anstatt polymorph zu sein:

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

Dann wird der Algorithmus langsamer wird. Tatsächlich scheint es jetzt in exponentieller Zeit zu laufen!

Bedeutet das Umschalten auf eine Signatur vom Typ "Polymorph", dass die Liste in jeder Phase vollständig neu berechnet wird? Wenn ja warum?

Answer 1

Dies ist wegen der Wörterbuchübersetzung.

fib :: [Int] 

ist eine Top-Level-Konstante.

Aber:

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

ist nur eine Top-Level-Funktion, die zu einem Num Wörterbuch zur Laufzeit angewandt werden. Wie so:

fib d = 1 : 1 : zipWith (d.+) (fib d) (tail (fib d)) 

Also, wenn Sie diese kompilieren ohne Optimierungen, so dass keine Spezialisierung passieren können, werden Sie mit exponentieller Zeit fib am Ende, wie die Liste von Grund auf neu erstellt wird, auf jedem Funktionsaufruf - es ist keine faule Datenstruktur mehr.

Answer 2

Ja, die Unterschrift des polymorphen Typs bedeutet, dass sie in jeder Phase neu berechnet wird. Der Kern hergestellt von GHC-7.4.2 mit -O2:

lvl_rcZ :: GHC.Integer.Type.Integer 
[GblId, Str=DmdType] 
lvl_rcZ = __integer 1 

Rec { 
PolyFib.fib [Occ=LoopBreaker] 
    :: forall a_a9W. GHC.Num.Num a_a9W => [a_a9W] 
[GblId, Arity=1, Str=DmdType L] 
PolyFib.fib = 
    \ (@ a_aal) ($dNum_aam :: GHC.Num.Num a_aal) -> 
    GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.Types.: 
     @ a_aal 
     (GHC.Num.fromInteger @ a_aal $dNum_aam lvl_rcZ) 
     (GHC.List.zipWith 
      @ a_aal 
      @ a_aal 
      @ a_aal 
      (GHC.Num.+ @ a_aal $dNum_aam) 
      (PolyFib.fib @ a_aal $dNum_aam) 
      (case PolyFib.fib @ a_aal $dNum_aam of _ { 
       [] -> GHC.List.tail1 @ a_aal; 
       : _ xs_abD -> xs_abD 
      }))) 
end Rec } 

Der Grund dafür ist, dass es nicht möglich ist eine Liste von Fibonacci-Zahlen für jeden Typ zu Num Zugehörigkeit Cache und fib ist explizit eine polymorphe Wert, ist es daher wird überhaupt nicht zwischengespeichert.

Wenn Sie es zumindest für die Berechnung bei jeder Art cachen möchten, verwenden Sie eine lokale Liste

pfibs :: Num a => [a] 
pfibs = res 
    where 
    res = 1 : 1 : zipWith (+) res (tail res) 

funktioniert das Caching für jede Berechnung (so pfibs !! 500 zB schnell ist), da nun die Liste monomorphic ist in jede Berechnung. Es wird immer noch für jede Abfrage neu berechnet (es sei denn, Sie binden es an einen monomorphen Namen), aber nicht für jedes einzelne Listenelement.

*PolyFib> pfibs !! 999999 :: Int 
-4249520595888827205 
(0.31 secs, 137462088 bytes)