¿Cómo puedo fusionar dos mapas en la misma lista?

Question

Podríamos fusionamos dos recorridos más de la lista xs en la expresión

(map f xs, map g xs) 

al igual que

unzip (map (\x -> (f x, g x)) xs) 

¿Hay alguna reasearch en la realización de este tipo de fusión de forma automática?

(Hay un riesgo de crear una fuga de espacio aquí, si una de las listas devueltas se consume antes que el otro estoy más interesado en la prevención del recorrido extra sobre xs que el ahorro de espacio..)

Edit: De hecho, no estoy buscando aplicar la fusión a las listas reales de Haskell en memoria, donde esta transformación podría no tener sentido dependiendo de si el unzip se puede fusionar con su (s) consumidor (s). Tengo una configuración donde sé que unzip puede fusionarse (ver "FlumeJava: tuberías de datos paralelas fáciles y eficientes").

Answer 1

También no es totalmente automático, pero puede darle a GHC una lista de reglas de reescritura como esa. Ver 7.14 Rewrite rules y Using rules. Entonces el compilador usa estas reglas para optimizar su programa al compilar. (Tenga en cuenta que el compilador de ninguna manera comprueba si las reglas tiene ningún sentido.)

Editar: Para dar un ejemplo de este problema en particular, podemos escribir:

{-# OPTIONS_GHC -fenable-rewrite-rules -ddump-rule-firings -ddump-rule-rewrites #-} 

import Data.Char 

{-# RULES 
"map/zip" forall f g xs. (,) (map f xs) (map g xs) = unzip (map (\x -> (f x, g x)) xs) 
    #-} 

main :: IO() 
main = let x = "abCD" in 
     print $ (,) (map toUpper x) (map toLower x) 

(el más alto nivel nombre de la función en la regla es (,) :: a -> b -> (a, b)). Al compilar, verá cómo se aplican las reglas. La opción dump-rule-firings muestra un mensaje cuando se aplica una regla y -ddump-rule-rewrites muestra cada aplicación de regla en detalle - consulte 7.14.6. Controlling what's going on in rewrite rules.

Answer 2

He conseguido encontrar dos recursos que menciona la fusión (des) zip como funciones, al menos brevemente:

Josef Svenningsson. "Acceso directo de fusión para acumular Parámetros Funciones & Zip-como" http://www.cse.chalmers.se/~josefs/publications/fusion.pdf

Duncan Coutts. "Stream Fusion: Práctica fusión de acceso directo para tipos de secuencia coinductiva" https://community.haskell.org/~duncan/thesis.pdf

Ninguno de los dos recursos menciona explícitamente este tipo de "fusión de hermanos".