Haskell: lista di fusione, dove è necessario?

Question

Diciamo che abbiamo la seguente:

l = map f (map g [1..100]) 

e vogliamo fare:

head l 

Così otteniamo:

head (map f (map g [1..100])) 

Ora, dobbiamo ottenere il primo elemento di Questo. map è definito qualcosa in questo modo:

map f l = f (head l) : (map f (tail l)) 

Allora otteniamo:

f (head (map g [1..100])) 

e poi applicato ancora:

f (g (head [1..100])) 

che si traduce in

f (g 1) 

No intermedio Li le m sono formate, semplicemente a causa della pigrizia.

Questa analisi è corretta? E con strutture semplici come questa:

foldl' ... $ map f1 $ map f2 $ createlist 

sono liste intermedie mai create, anche senza "lista fusion"? (Penso che la pigrizia dovrebbe eliminarli banalmente).

---

L'unico posto dove posso vedere un motivo per mantenere una lista è se abbiamo fatto:

l' = [1..100] 
l = map f (map g l') 

Dove potremmo voler mantenere l', se viene usato altrove. Tuttavia, nel caso l' qui sopra, dovrebbe essere abbastanza banale per il compilatore rendersi conto più rapidamente solo per ricalcolare l'elenco sopra che memorizzarlo.

Answer 1

Nell'esempio map vengono create le celle dell'elenco e quindi raccolte immediatamente. Con la fusione delle liste non è necessario alcun GC o manipolazione del thunk (che non sono entrambi gratuiti).

Answer 2

La fusion beneficia maggiormente quando le strutture dati intermedie sono costose. Quando la struttura che viene passata è pigra e vi si accede in modo sequenziale, le strutture possono essere relativamente economiche (come nel caso delle liste).

• Per le strutture pigre, la fusione rimuove il fattore costante di creazione di un thunk e immediatamente la raccolta dei dati.
• Per strutture rigide, la fusione può rimuovere O (n) lavoro.

I maggiori vantaggi sono quindi per array rigidi e strutture simili. Tuttavia, persino la fusione di elenchi pigri è ancora una vittoria, a causa della maggiore localizzazione dei dati, a causa del minor numero di strutture intermedie assegnate come thunk.