foldl/foldr query

Question

Soy un principiante en Haskell, e incluso después de leer varias explicaciones de foldr/foldl, no puedo entender por qué obtengo diferentes resultados a continuación. ¿Cuál es la explicación?

Prelude> foldl (\_ -> (+1)) 0 [1,2,3] 
4 
Prelude> foldr (\_ -> (+1)) 0 [1,2,3] 
3 

¡Gracias!

Answer 1

En el caso foldl, la lambda se está pasando el acumulador como primer argumento, y el elemento de lista como el segundo. En el caso foldr, la lambda pasa el elemento lista como primer argumento y el acumulador como el segundo.

Su lambda ignora el primer argumento y agrega 1 al segundo, por lo que en el caso foldl está agregando 1 al último elemento, y en el caso foldr, está contando el número de elementos en la lista.

Answer 2

En foldl f, el acumulador es el argumento de la izquierda al f, que está ignorando, por lo que devuelve 1 + el último elemento. Con foldr, el acumulador es el argumento correcto, por lo que está aumentando el acumulador en 1 por cada elemento, dando efectivamente la longitud de la lista.

f x y = y + 1 

foldl f 0 [1, 2, 3] 
= f (f (f 0 1) 2) 3 
= f ignored 3 
= 3 + 1 
= 4 

foldr f 0 [1, 2, 3] 
= f 1 (f 2 (f 3 0))) 
= f ignored (f ignored (f ignored 0))) 
= ((((0 + 1) + 1) + 1) 
= 3 

Answer 3

La diferencia se debe a dos cosas:

• que estás descartando una entrada a la función de la acumulación y la aplicación de una función constante a la otra.
• El orden de los argumentos para la función de acumulación es diferente entre los dos.

Con la tapa izquierda, el acumulador es el argumento que descartes, por lo que cada vez que se va a aplicar (+1) al siguiente elemento de la lista y, finalmente, volver al último elemento más uno.

Con el doblez correcto, el acumulador es el argumento que guarda, por lo que cada vez que aplica (+1) al resultado anterior, que es 0 para comenzar y se incrementa tres veces (para cada elemento de la lista).

Puede ser que sea más fácil ver lo que está pasando aquí si se utiliza más, obviamente, los valores de entrada distintas:

Prelude> foldl (\_ -> (+1)) 100 [5,6,7] 
8 
Prelude> foldr (\_ -> (+1)) 100 [5,6,7] 
103 

Una vez más, "último argumento más uno" y "longitud de la lista de más valor inicial".

Answer 4

Esto se debe a que el orden de los argumentos se invierte en foldl. Compara sus firmas de tipos:

foldl :: (a -> b -> a) -> a -> [b] -> a 
foldr :: (a -> b -> b) -> b -> [a] -> b 

Como puede ver, en su código utilizando foldl, que repeatly incrementar el acumulador, haciendo caso omiso de la lista. Pero en el código con foldr, ni siquiera toca el acumulador, sino que simplemente incrementa el elemento de la lista. Como el último elemento es 3, el resultado es 3 + 1 = 4.

Se podía ver su misstake más fácil, si tendrá que utilizar una lista de caracteres también conocido como cadena en lugar:

 
ghci> foldr (\_ -> (+1)) 0 ['a','b','c'] 
3 
ghci> foldl (\_ -> (+1)) 0 ['a','b','c'] 

:1:20: 
    No instance for (Num Char) 
     arising from the literal `0' 
    Possible fix: add an instance declaration for (Num Char) 
    In the second argument of `foldl', namely `0' 
    In the expression: foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c'] 
    In an equation for `it': 
     it = foldl (\ _ -> (+ 1)) 0 ['a', 'b', 'c'] 
ghci> 

Answer 5

Eliminar el estilo de currying y sin puntos puede ayudar.Sus dos expresiones se equivilent a:

foldl (\acc x -> x + 1) 0 [1,2,3] 
foldr (\x acc -> acc + 1) 0 [1,2,3] 

Cuando se ve como tal, los resultados deben aparecer más evidente