Warum wirkt sich ein allgemeinerer Typ auf die Laufzeit in Haskell aus?

Question

Betrachten Sie die beiden folgenden Implementierungen einer unendlichen Fibonacci-Folge:

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

fibsB :: [Integer] 
fibsB = 0:1:(zipWith (+) fibsB (tail fibsB)) 

In GHCI, als fibsB !! k ist viel schneller Ausführung fibsA !! k ausführt. Insbesondere scheint es, dass die Werte von fibsA kontinuierlich neu berechnet werden (nicht gespeichert/gespeichert).

Darüber hinaus zeigt GHCIs :t[Integer], wenn die Typensignatur fehlt, und die Funktion führt entsprechend aus. Dieses Verhalten tritt auch in kompiliertem Code auf (ghc -O3 Fibs.hs).

Warum ist Integer so viel schneller als Num a => a?

Answer 1

Wenn Sie fibsA :: Num a => [a] schreiben, erstellt der Compiler, was im Wesentlichen

fibsA :: NumDict a -> [a] 

Wo

data NumDict a = NumDict 
    { (+)   :: a -> a -> a 
    , (-)   :: a -> a -> a 
    , (*)   :: a -> a -> a 
    , negate  :: a -> a 
    , abs   :: a -> a 
    , signum  :: a -> a 
    , fromInteger :: Integer -> a 
    } 

Beachten Sie, dass Num a sich von einem Zwang zu sein ein Argument an die Funktion bewegt hat. A typeclass is essentially just a lookup table for each type that implements the class. Also für Num, würden Sie haben standardmäßig

mkInteger_NumDict :: NumDict Integer 
mkInteger_NumDict = NumDict 
    { (+) = integer_plus 
    , (-) = integer_minus 
    , (*) = integer_mult 
    , ... 
    } 

mkInt_NumDict  :: NumDict Int 

mkFloat_NumDict :: NumDict Float 

mkDouble_NumDict :: NumDict Double 

und diese werden automatisch an eine Funktion übergeben ein typeclass verwenden, wenn die Instanz behoben ist. Dies bedeutet, dass unsere Funktion fibsA im Wesentlichen ein Argument annimmt. Wenn Sie es aus GHCi nennen, treten die säumigen Regeln und Integer holen, aber da ist es auf diese Weise gefordert wird, würde es eher wie diese intern aussehen:

{-# RecordWildCards #-} -- To reduce typing 

fibsA :: NumDict a -> [a] 
fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) (fibsA nd) (tail $ fibsA nd) 

Sehen Sie das Problem mit diesem? Es ist immer noch rekursiv, aber jetzt muss es bei jedem Schritt eine Funktion aufrufen, um die Leistung zu reduzieren. Wenn Sie es wirklich schnell machen wollten, würde ein intelligenter Programmierer tun

fibsA nd@(NumDict{..}) = fromInteger 0 : fromInteger 1 : zipWith (+) fibsA' (tail fibsA') 
    where fibsA' = fibsA nd 

Dies zumindest ermöglicht Memoisierung. Eine Haskell-Binärdatei kann diese Optimierung jedoch nicht wirklich zur Laufzeit ausführen, was zur Kompilierungszeit geschieht. Was Sie am Ende haben, ist eine langsamere rekursive Funktion. Mit fibsB geben Sie den Typ konkret an, es gibt keine polymorphen Einschränkungen für die Typensignatur. Der Wert fibsB enthält keine impliziten oder expliziten Argumente. Wenn Sie darauf verweisen, handelt es sich um einen Zeiger auf dasselbe Objekt im Speicher. fibsA ist ein Zeiger auf eine Funktion. Wenn sie rekursiv verwendet wird, gibt sie neue Objekte im Speicher zurück und hat keine Memo-Funktion. Deshalb ist fibsB schneller als fibsA, nur fibsB wird optimiert, weil der Compiler es nicht für alle Num, nur Integer arbeiten lassen muss.

Answer 2

Neben @ bheklilr ist gründliche Erklärung: Sie können auch fibsA schnell machen, wenn Sie die Liste Sharing innerhalb der Funktion auszuführen, ist es nicht-rekursive (Ausblenden der Rekursion innen) machen:

fibsA' :: Num a => [a] 
fibsA' = 
    let f = 0:1:(zipWith (+) f (tail f)) 
    in f