foldr y foldl más explicaciones y ejemplos

Question

He mirado en diferentes pliegues y plegable en general, así como algunos otros y lo explican bastante bien.

Todavía estoy teniendo problemas en cómo una lambda funcionaría en este caso.

foldr (\y ys -> ys ++ [y]) [] [1,2,3]

Podría alguien ir a través de ese paso a paso y tratar de explicar que a mí?

Y también cómo se foldl trabajo?

Answer 1

Uso

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

y

k y ys = ys ++ [y]

Vamos a deshacer las maletas:

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

Answer 2

foldr es una cosa fácil:

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

Se necesita una función que es de alguna manera similar a (:),

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

y un valor que es similar a la lista vacía [],

[] :: [a]

y sustituye cada uno: y [] en alguna lista .

Se ve así:

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))

Se puede imaginar foldr como un estado-máquina-evaluador, también:

f es la transición,

f :: input -> state -> state

ye es el estado de inicio.

e :: state

foldr (foldRIGHT) se ejecuta la máquina de estados con el f de transición y el estado de inicio e sobre la lista de entradas, comenzando en el extremo derecho. Imagínese f en infija notación como el Pacman procedente de-RIGHT.

foldl (foldLEFT) hace lo mismo desde-izquierda, pero la función de transición, escrito en notación infija, toma su argumento de entrada de la derecha. Por lo que la máquina consume la lista que comienza en el extremo izquierdo. Pacman consume la lista de IZQUIERDA con la boca abierta a la derecha, a causa de la boca (b-> a-> b) en lugar de (A-> B-> b).

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

Para aclarar esto, imaginar el (-) función que la transición:

foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

foldr (-) 100 [1]         = -99 = (1-(100))
foldr (-) 100 [2,1]       = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1]     = -98 = (3-(101))
foldr (-) 100 [4,3,2,1]   = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))

Es posible que desee utilizar foldr en situaciones en las que la lista puede ser infinita, y donde la evaluación debe ser perezoso:

foldr (either (\l ~(ls,rs)->(l:ls,rs))
              (\r ~(ls,rs)->(ls,r:rs))
      ) ([],[]) :: [Either l r]->([l],[r])

Y es probable que desee utilizar la versión estricta de foldl, que es foldl', cuando se consume toda la lista para producir su salida. Se podría realizar mejor y desee evitar tener pila desbordamiento o excepciones fuera de la memoria (dependiendo del compilador), debido a las largas listas extremas en combinación con la evaluación perezosa:

foldl' (+) 0 [1..100000000] = 5000000050000000
foldl  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci

La primera -paso por paso- crea una entrada de la lista, lo evalúa y lo consume.

El segundo crea una fórmula muy largo en primer lugar, perdiendo la memoria con ((... ((0 + 1) 2) 3) + ...), y evalúa toda ella después.

El tercero es como el segundo, pero con la otra fórmula.

Answer 3

La definición de foldr es:

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

Así que aquí hay una reducción progresiva de su ejemplo:

  foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]

Answer 4

notación infija, probablemente será más claro aquí.

Empecemos con la definición:

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

En aras de la brevedad, vamos a g escritura en lugar de (\y ys -> ys ++ [y]). Las siguientes líneas son equivalentes:

foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]