foldr e foldl ulteriori spiegazioni ed esempi
-
08-10-2019 - |
Domanda
Ho guardato diverse pieghe e pieghevole in generale così come pochi altri e spiegano abbastanza bene.
Sto ancora problemi su come un lambda avrebbe funzionato in questo caso.
foldr (\y ys -> ys ++ [y]) [] [1,2,3]
Qualcuno potrebbe passare attraverso quel passo passo e cercare di spiegare che a me?
E anche come sarebbe foldl
lavoro?
Soluzione
con
foldr f z [] = z
foldr f z (x:xs) = x `f` foldr f z xs
E
k y ys = ys ++ [y]
Let decompressione:
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]
Altri suggerimenti
foldr è una cosa facile:
foldr :: (a->b->b) -> b -> [a] -> b
Ci vuole una funzione che è in qualche modo simile a (:),
(:) :: a -> [a] -> [a]
e un valore che è simile alla lista vuota [],
[] :: [a]
e sostituisce ogni: e [] in qualche lista ??p>.
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 è lo stato di avvio.
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. Immaginate f in infisso notazione come pacman provenienti da-DESTRA.
foldl (foldLEFT) fa lo stesso da-sinistra, ma la funzione di transizione, scritto in notazione infissa, prende il parametro di input da destra. Così la macchina consuma la lista a partire dalla fine sinistra. Pacman consuma l'elenco da-sinistra con la bocca aperta a destra, a causa della bocca (b-> a-> b) invece di (a-> b-> b).
foldl :: (b->a->b) -> b -> [a] -> b
Per rendere questa chiara, immaginate la funzione (-)
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 in cui 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 si 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 -step da passo- crea una voce della lista, valuta, e consuma.
Il secondo crea una lunghissima formula prima, sprecando memoria con ((... ((0 + 1) 2) 3) + ...), e valuta tutto in seguito.
Il terzo è simile al secondo, ma con l'altra formula.
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]
Infix notazione sarà probabilmente più chiaro qui.
La partenza di Let con la definizione:
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
Per ragioni di brevità, diamo g
scrittura invece di (\y ys -> ys ++ [y])
. Le righe seguenti 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]