Haskell: Lista de fusión, ¿dónde se necesita?

Question

digamos que tenemos el siguiente:

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

y queremos hacer:

head l 

por lo que tenemos:

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

Ahora, tenemos que el primer elemento de esta. map se define algo así:

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

Entonces obtenemos:

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

y luego se aplica una vez más:

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

que se traduce en

f (g 1) 

Sin intermedia li Los pts están formados, simplemente debido a la pereza.

¿Este análisis es correcto? Y con estructuras simples como esta:

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

¿Alguna vez se crearon listas intermedias, incluso sin "lista de fusión"? (Creo que la pereza debería eliminarlos trivialmente).

---

El único lugar donde puedo ver una razón para mantener una lista es que si lo hicimos:

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

donde puede ser que desee mantener l', si se utiliza en otros lugares. Sin embargo, en el caso l' aquí arriba, el compilador debería ser bastante trivial para darse cuenta de que es más rápido simplemente recalcular la lista anterior que almacenarla.

Answer 1

En su ejemplo map, se crean las celdas de la lista y luego se recogen de inmediato. Con la fusión de listas no se necesita GC o manipulación de thunk (que no son gratuitas).

Answer 2

Fusion se beneficia más cuando las estructuras de datos intermedias son costosas. Cuando la estructura que se pasa es holgazana, y se accede de forma secuencial, las estructuras pueden ser relativamente baratas (como es el caso de las listas).

• Para estructuras perezosos, fusión elimina el factor constante de la creación de un procesador, y de inmediato la basura recogida de ella.
• Para estructuras estrictas, la fusión puede eliminar O (n) trabajo.

Los mayores beneficios son, por tanto, para matrices estrictas y estructuras similares. Sin embargo, incluso la fusión de listas diferidas sigue siendo una victoria, debido al aumento de la ubicación de los datos, debido a la menor cantidad de estructuras intermedias asignadas como thunks.