En resumen, no tan a menudo como se podría pensar. La razón es que las "técnicas sofisticadas" como la fusión de secuencias se emplean cuando se implementan las bibliotecas, y los usuarios de la biblioteca no tienen que preocuparse por ellas.
Considere Data.List.map
. El paquete de base define map
como
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Este map
es auto-recursivo, por lo GHC no inline ella.
Sin embargo, base
define también los siguientes reglas de reescritura:
{-# RULES
"map" [~1] forall f xs. map f xs = build (\c n -> foldr (mapFB c f) n xs)
"mapList" [1] forall f. foldr (mapFB (:) f) [] = map f
"mapFB" forall c f g. mapFB (mapFB c f) g = mapFB c (f.g)
#-}
Esto reemplaza usos de map
través foldr/build fusion, entonces, si la función no se puede fusionar, lo reemplaza con el original map
. Debido a que la fusión ocurre automáticamente, no depende de que el usuario lo sepa.
Como prueba de que todo esto funciona, puede examinar lo que GHC produce para entradas específicas. Para esta función:
proc1 = sum . take 10 . map (+1) . map (*2)
eval1 = proc1 [1..5]
eval2 = proc1 [1..]
cuando se compila con -O2, GHC fusiona todos proc1
en una sola forma recursiva (como se ve en la salida de núcleo con -ddump-simpl
).
Por supuesto que estas técnicas tienen sus límites.Por ejemplo, la función de promedio ingenuo, mean xs = sum xs/length xs
, se puede transformar fácilmente manualmente en un solo pliegue, y frameworks exist that can do so automatically, sin embargo, en la actualidad no hay forma conocida de traducir automáticamente entre las funciones estándar y el marco de fusión. Entonces, en este caso, el usuario debe ser consciente de las limitaciones del código producido por el compilador.
Por lo tanto, en muchos casos los compiladores son lo suficientemente avanzados para crear código que es rápido y elegante. Sabiendo cuándo lo harán, y cuándo es probable que el compilador se caiga, en mi humilde opinión, una gran parte de aprender a escribir un código Haskell eficiente.
He editado en los enlaces por usted y votado en alza. ¡Gran respuesta! – ehird
Ahh, maravilloso, esto pinta una imagen mucho más clara, ¡gracias! –
Quizás quiso decir 'g (x: xs) = 2 * x: g xs'? – pat