foldr e foldl ulteriori spiegazioni ed esempi

Question

Ho dato un'occhiata a different folds e folding in general così come a pochi altri e lo spiegano abbastanza bene.

Ho ancora problemi su come un lambda potrebbe funzionare in questo caso.

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

Qualcuno potrebbe analizzarlo passo dopo passo e provare a spiegarmelo.

E come funzionerebbe anche lo foldl.

Answer 1

Utilizzando

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

E

k y ys = ys ++ [y] 

unpack

Let:

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 definizione di foldr è:

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

Quindi, ecco un passo per ridurre passo del vostro esempio:

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

Infix notazione sarà probabilmente più chiaro qui. inizio

Let con la definizione:

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

Per brevità, scriviamo g invece di (\y ys -> ys ++ [y]). Le seguenti linee sono equivalenti:

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 è una cosa facile:

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

Si prende una funzione che è in qualche modo simile a (:),

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

ed un valore che è simile alla lista vuota [],

[] :: [a] 

e sostituisce ciascuno: e [] in qualche elenco.

Ecco come si presenta:

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

si può immaginare foldr alcuni state-machine-valutatore, anche:

f è la transizione,

f :: input -> state -> state 

ed e è il stato di partenza.

e :: state 

foldr (foldRIGHT) gestisce lo stato della macchina con la f transizione e lo stato di avvio e sopra l'elenco degli ingressi, iniziando all'estremità destra.Immagina la notazione infix come il pacman proveniente da -DEST.

foldl (foldLEFT) fa lo stesso da-sinistra, ma la funzione di transizione, scritto in notazione infissa, prende il parametro di input da destra. Quindi la macchina consuma la lista iniziando dall'estremità sinistra. Pacman consuma l'elenco da -L'ALTRO con una bocca aperta a destra, a causa della bocca (b-> a-> b) invece di (a-> b-> b).

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

Per chiarire questo punto, immaginiamo la funzione meno come di transizione:

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

Probabilmente si desidera utilizzare foldr in situazioni, dove la lista può essere infinita, e dove la valutazione dovrebbe essere pigro:

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

E probabilmente desidera utilizzare la versione rigorosa della foldl, che è foldl', quando si consuma l'intera lista per produrre il suo output. Potrebbe funzionare meglio e potrebbe evitare di dover stack overflow o eccezioni out-of-memoria (a seconda del compilatore) a causa di lunghe liste estremi in combinazione con la valutazione pigra:

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 

Il primo passo -step - crea una voce dell'elenco, la valuta e la consuma.

Il secondo crea una formula molto lunga prima, sprecando memoria con ((... ((0 + 1) +2) +3) + ...), e valuta tutto in seguito.

Il terzo come il secondo, ma con l'altra formula.