¿Cómo funciona foldr?

Question

¿Alguien puede explicar cómo funciona foldr?

Tome estos ejemplos:

Prelude> foldr (-) 54 [10, 11] 
53 
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6] 
12.0 

Estoy confundido acerca de estas ejecuciones. ¿Alguna sugerencia?

Answer 1

foldr comienza en el extremo derecho de la lista y combina cada entrada de la lista con el valor del acumulador con la función que le asigna. El resultado es el valor final del acumulador después de "plegar" en todos los elementos de la lista. Su tipo es:

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

y desde este se puede ver que el elemento de la lista (de tipo a) es el primer argumento de la función dada, y el acumulador (de tipo b) es el segundo.

Para su primer ejemplo:

Starting accumulator = 54 
11 - 54 = -43 
10 - (-43) = 53 

     ^Result from the previous line 

^ Next list item 

Así que la respuesta se obtuvo fue 53.

El segundo ejemplo:

Starting accumulator = 54 
(6 + 54)/2 = 30 
(10 + 30)/2 = 20 
(4 + 20)/2 = 12 
(12 + 12)/2 = 12 

Así, el resultado es 12.

Editar : Quise agregar, eso es para listas finitas. foldr también puede funcionar en listas infinitas, pero lo mejor es primero que nada pensar en el caso finito, creo.

Answer 2

foldr significa pliegue desde la derecha, por lo que foldr (-) 0 [1, 2, 3] produce (1 - (2 - (3 - 0))). En comparación, foldl produce (((0 - 1) - 2) - 3).

Cuando los operadores no son commutativefoldl y foldr obtendrán resultados diferentes.

En su caso, el primer ejemplo se expande a (10 - (11 - 54)) lo que da 53.

Answer 3

Piense en foldr 's muy definition:

-- if the list is empty, the result is the initial value z 
foldr f z []  = z     
-- if not, apply f to the first element and the result of folding the rest 
foldr f z (x:xs) = f x (foldr f z xs) 

Así, por ejemplo foldr (-) 54 [10,11] debe ser igual a (-) 10 (foldr (-) 54 [11]), es decir, a expandirse de nuevo, igual (-) 10 ((-) 11 54). Entonces la operación interna es 11 - 54, es decir, -43; y la operación externa es 10 - (-43), es decir, 10 + 43, por lo tanto 53 como observa. Siga pasos similares para su segundo caso, y de nuevo verá cómo se forma el resultado.

Answer 4

Siempre he pensado que http://foldr.com es una ilustración divertida. Vea la publicación Lambda the Ultimate.

Answer 5

La manera más fácil de entender foldr es reescribir la lista en la que está doblando sin el azúcar.

[1,2,3,4,5] => 1:(2:(3:(4:(5:[])))) 

ahora foldr f x lo que hace es que reemplaza cada : con f en forma infija y [] con x y evalúa el resultado.

Por ejemplo:

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

[1,2,3] === 1:(2:(3:[])) 

por lo

sum [1,2,3] === 1+(2+(3+0)) = 6 

Answer 6

Una manera fácil de entender foldr es la siguiente: Se reemplaza todas las listas de constructor con una aplicación de la función prevista. Su primer ejemplo se traduciría en:

10 - (11 - 54)

de:

10 : (11 : [])

Un buen consejo que obtuve de la Haskell Wikibook podría ser de alguna utilidad aquí:

Como regla general, debe usar foldr en listas que pueden ser infinitas o donde el pliegue está creando una estructura de datos, y foldl' si se sabe que la lista es finita y se reduce a un único valor. foldl (sin la marca) rara vez se debe utilizar.

Answer 7

Ayuda a entender la distinción entre foldr y foldl. ¿Por qué se llama foldr "doblar a la derecha"?

Inicialmente pensé que era porque consumía elementos de derecha a izquierda. Sin embargo, tanto foldr como foldl consumen la lista de izquierda a derecha.

• foldlevalúa de izquierda a derecha (asociativo izquierda)
• foldrevalúa de derecha a izquierda (asociativo por la derecha)

Podemos hacer esta distinción clara con un ejemplo que usa un operador para el cual importa la asociatividad. Podríamos utilizar un ejemplo humano, tales como el operador, "come":

foodChain = (human : (shark : (fish : (algae : [])))) 

foldl step [] foodChain 
    where step eater food = eater `eats` food -- note that "eater" is the accumulator and "food" is the element 

foldl `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldl eats (human `eats` shark)        (fish : (algae : [])) 
    == foldl eats ((human `eats` shark) `eats` fish)    (algae : []) 
    == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) [] 
    ==   (((human `eats` shark) `eats` fish) `eats` algae) 

La semántica de esta foldl es: Un ser humano come un poco de tiburón, y luego el mismo ser humano que ha comido tiburón entonces come algunos peces, etc. El que come es el acumulador.

Contraste esto con:

foldr step [] foodChain 
    where step food eater = eater `eats` food. -- note that "eater" is the element and "food" is the accumulator 

foldr `eats` [] (human : (shark : (fish : (algae : [])))) 
    == foldr eats (human `eats` shark)        (fish : (algae : [])))) 
    == foldr eats (human `eats` (shark `eats` (fish))    (algae : []) 
    == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) [] 
    ==   (human `eats` (shark `eats` (fish `eats` algae) 

La semántica de esta foldr es: Un humano come un tiburón que ya ha comido un pez, que ya ha comido algunas algas. La comida es el acumulador.

Ambos foldl y foldr "despegan" a los devoradores de izquierda a derecha, así que esa no es la razón por la que nos referimos a foldl como "pliegue izquierdo". En cambio, el orden de la evaluación importa.

Answer 8

Ok, veamos los argumentos:

• una función (que lleva un elemento de lista y un valor (un posible resultado parcial) del mismo tipo del valor que devuelve);
• una especificación del resultado inicial para la lista vacía caso especial
• una lista;

valor de retorno:

• algún resultado final

Se aplica por primera vez la función hasta el último elemento de la lista y el resultado lista vacía. A continuación, vuelve a aplicar la función con este resultado y el elemento anterior, y así sucesivamente hasta que tome algún resultado actual y el primer elemento de la lista para devolver el resultado final.

Doblar "pliega" una lista alrededor de un resultado inicial usando una función que toma un elemento y un resultado de plegado anterior. Repite esto para cada elemento. Entonces, foldr hace esto comenzando al final de la lista, o al lado derecho de la misma.

folr f emptyresult [1,2,3,4] se convierte en f(1, f(2, f(3, f(4, emptyresult)))). Ahora solo sigue paréntesis en evaluación y listo.

Una cosa importante de notar es que la función suministrada f debe manejar su propio valor de retorno ya que su segundo argumento, que implica que ambos deben tener el mismo tipo.

Fuente: my post donde lo miro desde una perspectiva imperdonable de javascript incierta si cree que podría ser útil.

Answer 9

Creo que implementar map, foldl y foldr de una manera simple ayuda a explicar cómo funcionan. Los ejemplos trabajados también ayudan en nuestra comprensión.

myMap f [] = [] 
    myMap f (x:xs) = f x : myMap f xs 

    myFoldL f i [] = i 
    myFoldL f i (x:xs) = myFoldL f (f i x) xs 

    > tail [1,2,3,4] ==> [2,3,4] 
    > last [1,2,3,4] ==> 4 
    > head [1,2,3,4] ==> 1 
    > init [1,2,3,4] ==> [1,2,3] 

    -- where f is a function, 
    -- acc is an accumulator which is given initially 
    -- l is a list. 
    -- 
    myFoldR' f acc [] = acc 
    myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l) 

    myFoldR f z []  = z 
    myFoldR f z (x:xs) = f x (myFoldR f z xs) 

    > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 
    > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0] 

    > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 
    > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125 

    foldl from above: Starting accumulator = 54 
     (12 + 54)/2 = 33 
     (4 + 33)/2 = 18.5 
     (10 + 18.5)/2 = 14.25 
     (6 + 14.25)/2 = 10.125` 

> foldr (++) "5" ["1", "2", "3", "4"] ==> "12345" 

> foldl (++) "5" ["1", "2", "3", "4"] ==> “51234" 

> foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 
> myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12 

    foldr from above: Starting accumulator = 54 
     (6 + 54)/2 = 30 
     (10 + 30)/2 = 20 
     (4 + 20)/2 = 12 
     (12 + 12)/2 = 12