Perché un tipo più generale influisce sul runtime in Haskell?

Question

considerare i due seguenti implementazioni di una sequenza di Fibonacci infinita:

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

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

In GHCI, l'esecuzione fibsB !! k è molto più veloce di esecuzione fibsA !! k. In particolare, sembra che i valori di fibsA vengano continuamente ricalcolati (non memoizzati/memorizzati).

Inoltre, quando viene omessa la firma del tipo, il codice :t di GHCI indica che è [Integer] e la funzione viene eseguita di conseguenza.

Questo comportamento si verifica anche nel codice compilato (ghc -O3 Fibs.hs).

Perché è il caso che Integer è molto più veloce di Num a => a?

Answer 1

Quando si scrive fibsA :: Num a => [a], il compilatore costruisce ciò che è essenzialmente

fibsA :: NumDict a -> [a] 

Dove

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 
    } 

noti che Num a ha spostato dall'essere un vincolo ad essere un argomento per la funzione. A typeclass is essentially just a lookup table for each type that implements the class. Così per Num, devi avere di default

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 

e questi ottiene automaticamente passato a una funzione utilizzando un typeclass quando l'istanza viene risolto. Ciò significa che la nostra funzione fibsA accetta essenzialmente un argomento. Quando si chiama da GHCi, le regole inadempienti calci in e il ritiro Integer, ma dal momento che è stato chiamato in questo modo sarebbe più simile a questo internamente:

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

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

Vedete il problema con questo? È ancora ricorsivo, ma ora deve fare in modo che una funzione chiami ogni fase del processo, riducendo le prestazioni. Se vuoi renderlo veramente veloce, un programmatore intelligente dovrebbe fare

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

Questo almeno consente la memoizzazione. Tuttavia, un haskell binario non può realmente eseguire questa ottimizzazione in fase di runtime, che avviene al momento della compilazione. Quindi, quello che si finisce è una funzione ricorsiva più lenta. Con fibsB, si specifica concretamente il tipo, non ci sono vincoli polimorfici sulla sua firma del tipo. Il valore fibsB non ha argomenti impliciti o espliciti, quindi quando riferito a un puntatore allo stesso oggetto in memoria. fibsA è un puntatore a una funzione, quindi quando utilizzato in modo ricorsivo restituisce nuovi oggetti in memoria e non ha memoization. Questo è il motivo per cui fibsB è più veloce di fibsA, solo fibsB viene ottimizzato perché il compilatore non deve farlo funzionare per tutti Num, solo Integer.

Answer 2

Oltre a @ bheklilr c'è spiegazione approfondita: è anche possibile fare fibsA veloce, se si esegue la condivisione lista all'interno della funzione, il che rende non ricorsiva (nascondendo la ricorsione all'interno):

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