C'è una struttura di dati intermedi creata in list comprehensions

Question

Sembra che lo foldr compia una sorta di fusione con la comprensione delle liste, quindi richiede meno allocazione di memoria (11mb) rispetto a foldl (21mb) in questo ad es.

myfunc = sum $ foldr g acc [ f x | x <- xs ] 
f x = .. 
g x y = .. 

Qualcuno potrebbe spiegare come e perché? Anche come la valutazione pigra aiuta in questo.

Answer 1

Una piega sinistra non può produrre alcun output (parte del risultato) prima che abbia attraversato l'intera lista. A seconda della funzione che si piega, è possibile creare una grande struttura di dati o un grosso thunk, che utilizza molta memoria (può essere eseguito in memoria costante se si piega ad esempio (+) su un elenco di Int).

Una piega destra può, per le funzioni appropriate (che possono produrre un risultato [parziale] senza ispezionare il secondo argomento) produrre il risultato in modo incrementale, in modo che se il risultato viene consumato appropriatamente e l'elenco di input sia generato correttamente, il l'intero calcolo può essere eseguito in un piccolo spazio costante. Come detto sclv, si riduce sostanzialmente a un ciclo in questi casi.

Answer 2

Possiamo desugar la comprensione come, essenzialmente, map f xs. Se lo stai compilando, ghc dovrebbe effettivamente essere in grado di fondere la somma, la piega e la mappa in un unico passaggio: http://www.haskell.org/haskellwiki/Correctness_of_short_cut_fusion. Ma anche se non lo sei, la pigrizia è il tuo amico per l'utilizzo della memoria. L'elenco prodotto dalla mappa è pigro - f viene applicato solo quando richiesto. E f sarà richiesto solo quando il foldr lo richiederà. E dal momento che foldr sta chiaramente producendo un altro elenco (pigro), ogni fase dell'ovile viene richiesta solo per somma a turno. Quindi hai ancora ciascuna funzione applicata a turno, ma non hai bisogno di produrre tutte le strutture intermedie dei dati tutte in una volta. Mentre hai scritto un insieme di composizioni di funzioni integrali, il modello di valutazione tende a trattare questo particolare insieme di codice, forma un intero gruppo di mani che ondeggiano, un po 'come un ciclo (sebbene, senza fusione, un ciclo con una buona quantità di riferimento indiretto).

Answer 3

Questa è una funzionalità del compilatore GHC. Fondamentalmente, GHC può riconoscere quando un elenco viene utilizzato in una "pipeline" e può convertire l'intero costrutto nell'equivalente di uno while -loop in C che non assegna affatto un elenco.

Il motivo per cui questo funziona con foldr e non foldl dipende dalla funzione g che si sta utilizzando nell'esempio. Dal foldr, al posto di , si accumula il risultato della funzione data come parametro (alias: foldl necessita dell'intera lista prima che possa iniziare effettivamente la valutazione della funzione g, quindi crea un enorme "thunk" di funzioni non valutate e l'ultimo elemento della lista come risultato - ecco perché in questo caso usa molta più memoria - mentre foldr può iniziare a valutare g non appena riceve un input di lista), è chiamato "strict" nel suo accumulatore, e alcune supposizioni possono essere fatte dal compilatore che può portare a ottimizzazioni.

Se, per esempio, la funzione g produce un valore che è un elenco, può continuare la suddetta strategia di ottimizzazione "pipeline", in pratica trattando il foldr come un map e rendendo l'intero costrutto (dalla generazione dell'elenco elencare consumo) in un ciclo rigoroso. Questo è possibile solo perché lo foldr produce esattamente un elemento di lista per ogni elemento di lista che consuma, il che non è garantito a foldl (specialmente per gli elenchi infiniti).