haskell combinators fold

haskell - ¿Cómo funciona foldr?



combinators (9)

Ayuda a entender la distinción entre foldr y foldl . ¿Por qué foldr llama "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.

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

Podemos aclarar esta distinción con un ejemplo que utiliza un operador para el cual importa la asociatividad. Podríamos usar un ejemplo humano, 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 este foldl es: un humano se come un tiburón, y luego el mismo humano que ha comido tiburón luego come un pez, etc. El que come es el acumulador.

Compare 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 este foldr es: Un humano come un tiburón que ya ha comido un pez, que ya ha comido algas. La comida es el acumulador.

Tanto foldl como foldr "despegan" a los comedores 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.

¿Alguien puede explicar cómo funciona foldr ?

Toma 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?

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

La forma 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 lo que foldr fx hace es que reemplaza a cada uno : 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:[]))

asi que

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

Ok, veamos los argumentos:

  • una función (que toma 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 el caso especial de la lista vacía
  • una lista;

valor de retorno:

  • algún resultado final

Primero aplica la función al último elemento de la lista y al resultado de la 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] 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 f debe manejar su propio valor de retorno como su segundo argumento, lo que implica que ambos deben tener el mismo tipo.

Fuente: mi publicación donde la miro desde una perspectiva imperativa de javascript incierta si cree que podría ser útil.

Piensa en la foldr de foldr :

-- 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)

Entonces, por ejemplo, foldr (-) 54 [10,11] debe ser igual (-) 10 (foldr (-) 54 [11]) , es decir expandir nuevamente, 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 se observa. Siga pasos similares para su segundo caso, y de nuevo verá cómo se forma el resultado.

Una manera fácil de entender foldr es esta: reemplaza a cada constructor de lista con una aplicación de la función provista. Su primer ejemplo se traduciría en:

10 - (11 - 54)

de:

10 : (11 : [])

Un buen consejo que obtuve de Haskell Wikilibro podría ser útil aquí:

Como regla, 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 en absoluto.

foldr comienza en el extremo derecho de la lista y combina cada entrada de la lista con el valor del acumulador usando 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 de esto se puede ver que el elemento de lista (de tipo a ) es el primer argumento para 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

Entonces la respuesta que obtuviste fue 53.

El segundo ejemplo:

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

Entonces el resultado es 12.

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

foldr significa plegar 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 commutative foldl y foldr obtendrán resultados diferentes.

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