suma - takewhile haskell

¿Por qué foldr usa una función de ayuda?

Question

Al explicar foldr a los novatos de Haskell, la definición canónica es

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

Pero en GHC.Base, foldr se define como

foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys

Parece que esta definición es una optimización de la velocidad, pero no veo por qué usar la función de ayuda sería más rápido. Los comentarios de la fuente ( ver aquí ) mencionan la inclusión en línea, pero tampoco veo cómo esta definición mejoraría la inclusión en línea.

Answer 1

Como dicen los comentarios:

-- Inline only in the final stage, after the foldr/cons rule has had a chance
-- Also note that we inline it when it has *two* parameters, which are the
-- ones we are keen about specialising!

En particular, tenga en cuenta que "lo incorporamos cuando tiene dos parámetros, ¡cuáles son los que nos interesa especializar!"

Lo que esto foldr decir es que cuando foldr se foldr , se está alineando solo para la elección específica de f y z , no para la elección de la lista que se dobla. No soy un experto, pero parece que permitiría integrarlo en situaciones como

map (foldr (+) 0) some_list

de modo que el en línea ocurra en esta línea y no después de que se haya aplicado el map Esto lo hace optimizable en más situaciones y más fácilmente. Lo que hace la función auxiliar es enmascarar el tercer argumento para que {-# INLINE #-} pueda hacer su trabajo.

Answer 2

GHC no puede en línea funciones recursivas, por lo que

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)

no puede ser en línea Pero

foldr k z = go
where
go [] = z
go (y:ys) = y `k` go ys

No es una función recursiva. ¡Es una función no recursiva con una definición recursiva local!

Esto significa que, como escribe @bheklilr, en el map (foldr (+) 0) el foldr puede estar en línea y, por lo tanto, f y z reemplazados por (+) y 0 en el nuevo go , y pueden suceder grandes cosas, como el desempaquetado de El valor intermedio.

Answer 3

Puedo agregar algunos detalles importantes sobre el sistema de optimización de GHC.

La definición ingenua de foldr pasa alrededor de una función. Existe una sobrecarga inherente al llamar a una función, especialmente cuando la función no se conoce en el momento de la compilación. Sería muy bueno poder en línea la definición de la función si se conoce en el momento de la compilación.

Hay trucos disponibles para realizar esa incorporación en GHC, y este es un ejemplo de ellos. Primero, foldr necesita estar en línea (veré por qué más adelante). La implementación ingenua de foldr es recursiva, por lo que no puede estar en línea. Por lo tanto, se aplica una transformación de trabajador / envoltorio a la definición. El trabajador es recursivo, pero la envoltura no lo es. Esto permite que foldr esté en línea, a pesar de la recursión sobre la estructura de la lista.

Cuando foldr está en línea, también crea una copia de todos sus enlaces locales. Es más o menos un alineamiento textual directo (modulo algo de cambio de nombre, y ocurre después del pase de desugaring). Aquí es donde las cosas se ponen interesantes. go es un enlace local, y el optimizador puede mirar dentro de él. Observa que llama a una función en el ámbito local, que denomina k . GHC a menudo eliminará la variable k completo, y la reemplazará con la expresión que k reduce a. Y luego, si la aplicación de la función se puede alinear, se puede alinear en este momento, eliminando la sobrecarga de llamar a una función de primera clase por completo.

Veamos un ejemplo simple y concreto. Este programa hará eco de una línea de entrada con todos los caracteres ''x'' finales eliminados:

dropR :: Char -> String -> String
dropR x r = if x == ''x'' && null r then "" else x : r
main :: IO ()
main = do
s <- getLine
putStrLn $ foldr dropR "" s

Primero, el optimizador incorporará la definición de foldr y simplificará, dando como resultado un código que se foldr así:

main :: IO ()
main = do
s <- getLine
-- I''m changing the where clause to a let expression for the sake of readability
putStrLn $ let { go [] = ""; go (x:xs) = dropR x (go xs) } in go s

Y eso es lo que permite la transformación de trabajador-envoltura. Voy a omitir los pasos restantes, pero debería ser obvio que GHC ahora puede dropR la definición de dropR , eliminando la sobrecarga de llamadas a funciones. Aquí es de donde viene la gran victoria de rendimiento.

Answer 4

Un pequeño detalle importante que no se menciona en otras respuestas es que GHC, dada una definición de función como

f x y z w q = ...

no puede insertar en línea f hasta que se apliquen todos los argumentos x , y , z , w y q . Esto significa que a menudo es ventajoso utilizar la transformación trabajador / envoltorio para exponer un conjunto mínimo de argumentos de función que deben aplicarse antes de que pueda ocurrir la incorporación.