¿Cómo funciona foldr?

Question

¿Alguien puede explicar cómo lo hace foldr trabajar?

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 acumulador usando la función que le des. El resultado es el valor final del acumulador después de "plegable" 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.

Edit: Me refería a añadir, eso es para las listas finitas. foldr también puede trabajar en listas infinitas, pero lo mejor es conseguir su cabeza en torno al caso finito primera, creo.

Answer 2

La forma más fácil de entender foldr es volver a escribir la lista que estés doblando sin el azúcar.

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

Ahora lo foldr f x 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:[]))

so

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

Answer 3

Ayuda a entender la distinción entre foldr y foldl. ¿Por qué es foldr denominado "pliegue correcto"?

Al principio pensé que era porque consume elementos de derecha a izquierda. Sin embargo, tanto foldr y foldl consumen la lista de izquierda a derecha.

• foldl evalúa de izquierda a derecha (asociativo por la izquierda)
• foldr evalúa de derecha a izquierda (asociativo por la derecha)

Podemos hacer esta distinción clara con un ejemplo que utiliza un operador de materias que 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 comedor 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.

Tanto foldl y foldr "pelar" comedores de izquierda a derecha, de manera que no es la razón nos referimos a foldl como "pliegue izquierda". En su lugar, el orden de las cuestiones de evaluación.

Answer 4

Piense de foldr muy definición :

 -- 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]), la expansión es decir, de nuevo, igual (-) 10 ((-) 11 54). Por lo que 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 mientras observa. Ir a través de pasos similares para su segundo caso, y de nuevo se verá cómo los formularios de resultados!

Answer 5

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

Cuando los operadores no son conmutativa foldl y foldr obtendrá resultados diferentes.

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

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 utilizar foldr en las listas que podrían ser infinito o cuando la tapa está la construcción de una estructura de datos, y foldl' si la lista se sabe que es finito y se reduce a un solo valor. foldl (sin la garrapata) rara vez se debe utilizar en absoluto.

Answer 7

Siempre he pensado http://foldr.com a ser un ejemplo de la diversión. Vea la Lambda el último puesto.

Answer 8

Creo que la aplicación de mapa, foldl y foldr de una manera sencilla ayuda a explicar cómo funcionan. Ejemplos resueltos también ayuda 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

Answer 9

Ok, veamos los argumentos:

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

valor de retorno:

• algún resultado final

En primer lugar, se aplica la función al ú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 se necesita algún resultado actual y el primer elemento de la lista para volver al resultado final.

plegar "pliegues" una lista alrededor de un resultado inicial usando una función que toma un elemento y un resultado de plegado anterior. Se repite esta operación para cada elemento. Así, foldr hace esto a partir del final de la lista, o el 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 sólo tienes que seguir paréntesis en la evaluación y eso es todo.

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

Fuente: mi post donde miro desde una perspectiva Javascript uncurried imprescindible si usted piensa que podría ayudar.