¿Qué es Stream Fusion de Haskell?

Question

¿Qué es Haskell's Stream Fusion y cómo lo uso?

Answer 1

El documento que señala Logan es genial, pero es un poco difícil. (Solo pregúntale a mis alumnos.) También es una gran oferta sobre 'cómo funciona la fusión de secuencias' y solo una fracción 'de qué es la fusión de secuencias y cómo puedes usarla'.

El problema que transmiten la fusión resuelve es que los códigos funcionales como está escrito menudo asignan listas intermedias, por ejemplo, para crear una lista infinita de números de nodo, es posible escribir

nodenames = map ("n"++) $ map show [1..] 

código Naive asignaría una lista infinita de enteros [1, 2, 3, ...], una lista infinita de cadenas ["1", "2", "3", ...], y finalmente una lista infinita de nombres ["n1", "n2", "n3", ...]. Eso es demasiada asignación.

Lo que hace stream fusion es traducir una definición como nodenames en algo que utiliza una función recursiva que asigna solo lo que se necesita para el resultado. En general, la eliminación de la asignación de listas intermedias se llama deforestación.

Para utilizar la fusión corriente, es necesario escribir funciones no recursivas lista que utilizan las funciones de la biblioteca de la corriente de fusión descrita en GHC ticket 915 (map, foldr, etc.) en lugar de recursividad explícita. Esta biblioteca contiene nuevas versiones de todas las funciones de Preludio que se han reescrito para aprovechar la fusión de secuencias. Aparentemente, esto está programado para llegar a la próxima versión de GHC (6.12) pero no está en la versión estable actual (6.10). Si desea usar la biblioteca, Porges tiene una explicación simple y agradable en su respuesta.

Si realmente desea una explicación de cómo funciona la fusión de secuencias, publique otra pregunta --- pero eso es mucho más difícil.

Answer 2

Hasta donde yo sé, y al contrario de lo que dijo Norman, la fusión de secuencias es no actualmente implementado en la base de GHC (es decir, no puede usar las funciones de Preludio). Para más información, vea GHC ticket 915.

Para usar la fusión de secuencias, debe instalar la biblioteca de fusión de secuencias, importar Data.List.Stream (también puede importar Control.Monad.Stream) y solo usar funciones de ese módulo en lugar de las funciones de Preludio. Esto significa importar el Preludio ocultando todas las funciones de lista predeterminadas, y no usar construcciones [x..y] ni enumerar la comprensión.

Answer 3

¿No es correcto, que cuando GHC en 6.12 usa esas nuevas funciones por defecto, que también implementarán [x..y] y enumerarán las comprensiones de esa manera no recursiva? Debido a que la única razón por la que no están en la fila correcta, es que son interno y no están realmente escritos en Haskell, sino más como palabras clave, por la velocidad y/o porque no sería posible redefinir esa sintaxis.