foldr y foldl más explicaciones y ejemplos

Question

He visto different folds y folding in general, así como algunos otros y lo explican bastante bien.

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

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

Podría alguien ir paso a paso y tratar de explicarme eso.

Y también cómo funcionaría foldl también.

Answer 1

Usando

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

Y

k y ys = ys ++ [y] 

unpack

Repasemos:

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

La definición de foldr es:

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

Así que aquí es 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 3

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

Vamos 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 escribir en lugar de g(\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] 

Answer 4

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 reemplaza cada uno: y [] en alguna lista.

Se ve así:

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

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

f es la transición,

f :: input -> state -> state 

y e es la 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.Imagina f en notación infija cuando el pacman viene de-DERECHO.

foldl (foldLEFT) hace lo mismo desde-IZQUIERDA, pero la función de transición, escrita en notación infija, toma su argumento de entrada desde la derecha. Entonces la máquina consume la lista comenzando en el extremo izquierdo. Pacman consume la lista desde-IZQUIERDA con la boca abierta hacia la derecha, debido a la boca (b-> a-> b) en lugar de (a-> b-> b).

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

Para aclarar esto, imaginemos el signo menos funcionan como 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 probablemente quiera 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 

El primero -paso a paso - crea una entrada de la lista, la evalúa y la consume.

El segundo crea primero una fórmula muy larga, desperdiciando memoria con ((... ((0 + 1) +2) +3) + ...), y luego evalúa todo.

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