foldr e foldl ulteriori spiegazioni ed esempi

Question

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?

Answer 1

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]

Answer 2

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 .

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.

Answer 3

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 4

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]