Perché l'aggiunta di una firma di tipo polimorfico peggiora le prestazioni?

Question

Ecco una semplice funzione per calcolare i numeri di Fibonacci:

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

In ghci posso calcolare la serie in fretta. In effetti, un po 'di sperimentazione rivela che il calcolo viene eseguito in un tempo approssimativamente lineare.

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

Se cambio la firma di tipo ad essere polimorfico invece:

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

Poi l'algoritmo diventa più lento. In effetti, sembra che ora funzioni in tempo esponenziale!

Il passaggio a una firma di tipo polimorfico significa che l'elenco viene completamente ricalcolato in ogni fase? Se è così, perché?

Answer 1

Ciò è dovuto alla traduzione del dizionario.

fib :: [Int] 

è una costante di primo livello.

Ma questo:

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

è solo una funzione di livello superiore, che sarà applicata a un dizionario Num in fase di esecuzione. In questo modo:

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

Quindi, se si compila questo senza alcuna ottimizzazione, in modo tale che nessuna specializzazione può accadere, si ritroverà con il tempo fib esponenziale, come la lista viene ricostruito da zero, su ogni chiamata di funzione - non è più una struttura dati pigra.

Answer 2

Sì, la firma del tipo polimorfico significa che viene ricalcolata in ogni fase. Il nucleo prodotto da ghc-7.4.2 con -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 } 

La ragione è che non è possibile mettere in cache un elenco di numeri di Fibonacci per ogni tipo facente Num, e fib è esplicitamente un valore polimorfica, quindi è non viene affatto memorizzato nella cache.

Se si desidera memorizzare nella cache almeno per il calcolo ad ogni tipo, utilizzare un elenco locale

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

fa la memorizzazione nella cache per ogni calcolo (in modo pfibs !! 500 esempio è veloce) dato che ora la lista è monomorfico in ogni calcolo. Sarà comunque ricalcolato per ogni query (a meno che non lo si colleghi a un nome monomorfico), ma non per ogni singolo elemento della lista.

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