Quando la memoizzazione è automatica in GHC Haskell?

Question

Io non riesco a capire il motivo per cui M1 appare memoized mentre m2 non è il seguente:

m1  = ((filter odd [1..]) !!) 

m2 n = ((filter odd [1..]) !! n) 

m1 10000000 richiede circa 1,5 secondi in prima convocazione, e una frazione di quello sulle chiamate successive (presumibilmente memorizza nella cache la lista), mentre m2 10000000 richiede sempre lo stesso tempo (ricostruendo l'elenco ad ogni chiamata). Qualche idea su cosa sta succedendo? Esistono regole pratiche per decidere se e quando GHC memorizzerà una funzione? Grazie.

Answer 1

GHC non memorizza le funzioni.

Tuttavia, calcola ogni espressione data nel codice al massimo una volta per volta in cui viene immessa l'espressione lambda circostante, o al massimo una volta mai se è al livello superiore. Determinare dove le lambda-espressioni sono può essere un po 'difficile quando si utilizzano zucchero sintattico, come nel tuo esempio, quindi cerchiamo di convertire questi per equivalente sintassi Dezuccherato:

m1' = (!!) (filter odd [1..])    -- NB: See below! 
m2' = \n -> (!!) (filter odd [1..]) n 

(Nota: Il rapporto Haskell 98 descrive in realtà un operatore di sinistra sezione come (a %) equivalenti a \b -> (%) a b, ma GHC desugars a (%) a. Queste sono tecnicamente differenti perché possono essere distinti da penso che potrei aver presentato un biglietto GHC Trac su questo seq..)

Detto questo, è possibile vedere che in m1', l'espressione filter odd [1..] non è contenuta n qualsiasi espressione lambda, quindi verrà calcolata una sola volta per ogni esecuzione del programma, mentre in m2', filter odd [1..] verrà calcolata ogni volta che viene immessa l'espressione lambda, ad esempio su ogni chiamata di m2'. Questo spiega la differenza di tempo che stai vedendo.

---

In realtà, alcune versioni di GHC, con determinate opzioni di ottimizzazione, condivideranno più valori di quanto indicato nella descrizione precedente. Questo può essere problematico in alcune situazioni. Ad esempio, si consideri la funzione

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x]) 

GHC potrebbe notare che y non dipende da x e riscrivere la funzione di

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x]) 

In questo caso, la nuova versione è molto meno efficiente perché avrà leggere circa 1 GB dalla memoria in cui è memorizzato , mentre la versione originale dovrebbe essere eseguita nello spazio costante e adattarsi alla cache del processore. In effetti, in GHC 6.12.1, la funzione f è quasi due volte più veloce quando è compilata senza le ottimizzazioni rispetto a quando è compilata con -O2.

Answer 2

m1 viene calcolato una sola volta perché è un modulo di domanda costante, mentre m2 non è un CAF, e quindi viene calcolato per ogni valutazione.

consultare il wiki GHC il CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

Answer 3

C'è una differenza fondamentale tra le due forme: la restrizione monomorfismo vale per m1, ma non M2, perché m2 ha dato esplicitamente argomenti. Quindi il tipo di m2 è generale ma quello di m1 è specifico.I tipi sono assegnati sono:

m1 :: Int -> Integer 
m2 :: (Integral a) => Int -> a 

compilatori La maggior parte Haskell e interpreti (tutti loro, che io sappia in realtà) non Memoize strutture polimorfiche, in modo lista interna di m2 viene ricreata ogni volta che si chiama, dove M1 di non è .

Answer 4

Non sono sicuro, perché sono abbastanza nuovo per Haskell, ma sembra che sia la seconda funzione parametrizzata e la prima no. La natura della funzione è quella, il suo risultato dipende dal valore di input e in particolare dal paradigma funzionale dipende SOLO dall'input. Ovvia implicazione è che una funzione senza parametri restituisce sempre lo stesso valore più e più volte, non importa quale.

A parte questo c'è un meccanismo di ottimizzazione nel compilatore GHC che sfrutta questo fatto per calcolare il valore di tale funzione una sola volta per tutto il tempo di esecuzione del programma. Lo fa pigramente, per essere sicuro, ma lo fa comunque. Ho notato anch'io, quando ho scritto la seguente funzione:

primes = filter isPrime [2..] 
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n] 
     where f `divides` n = (n `mod` f) == 0 

Poi Per provarlo, sono entrato GHCI e scrissi: primes !! 1000. Ci sono voluti alcuni secondi, ma alla fine ho ricevuto la risposta: 7927. Quindi ho chiamato primes !! 1001 e ho ottenuto la risposta all'istante. Allo stesso modo in un istante ho ottenuto il risultato per take 1000 primes, perché Haskell ha dovuto calcolare l'intero elenco di migliaia di elementi per restituire l'elemento 1001st prima.

Quindi se si può scrivere la propria funzione in modo tale che non ci siano parametri, probabilmente lo si desidera. ;)