pieghevole. composizione della funzione foldr - Haskell

Question

Quindi, sto davvero friggendo il cervello cercando di capire la composizione di foldl.foldr. Ecco un esempio:

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

Il risultato è 22, ma ciò che sta realmente accadendo qui?

Per me sembra che questo sia quello che sta accadendo: foldl (+) 1 [6,15]. Il mio dubbio è relativo alla parte foldr. Non dovrebbe aggiungere l'1 a tutte le sotto-liste? In questo modo: foldr (+) 1 [1,2,3]. Nella mia testa l'1 è aggiunto solo una volta, giusto? (probabilmente no, ma voglio sapere come/perché!).

Sono molto confuso (e forse facendo tutta la confusione, ahah). Grazie!

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

diventa

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]] 

in modo da ottenere

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]] 

dopo la prima fase di foldl o

foldl (foldr (+)) 7 [[4,5,6]] 

se valutiamo il applicata foldr (a meno che lo stric analizzatore tness entra in gioco, sarebbe in realtà rimanere un thunk non valutata fino a quando il foldl ha attraversato l'intero elenco, ma la prossima espressione è più leggibile con esso analizzato), e che diventa

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) [] 

e infine

foldl (foldr (+)) 22 [] 
~> 22 

Answer 2

Esaminiamo foldl . foldr. I loro tipi sono

foldl :: (a -> b -> a) -> (a -> [b] -> a) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

intenzionalmente usato variabili di tipo distinte e ho aggiunto parentesi in modo che diventi più evidente che li consideriamo ora in funzione di un argomento (ed i loro risultati sono funzioni). Guardando a foldl vediamo che si tratta di una sorta di funzione di sollevamento: data una funzione che produce a da a usando b, la solleviamo in modo che funzioni su [b] (ripetendo il calcolo). La funzione foldr è simile, solo con gli argomenti invertiti.

Ora cosa succede se applichiamo foldl . foldr? Innanzitutto, deriviamo il tipo: dobbiamo unificare le variabili di tipo in modo che il risultato di foldr corrisponda all'argomento di foldl. Quindi dobbiamo sostituire: a = d, b = [c]:

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

in modo da ottenere

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d) 

E qual è il suo significato? Innanzitutto, foldr solleva l'argomento di tipo c -> d -> d per lavorare sugli elenchi e inverte i suoi argomenti in modo da ottenere d -> [c] -> d. Successivamente, foldl solleva nuovamente questa funzione per funzionare su [[c]] - elenchi di [c].

Nel tuo caso, l'operazione che si sta sollevando (+) è associativa, quindi non ci interessa l'ordine della sua applicazione. Il doppio sollevamento crea semplicemente una funzione che applica l'operazione su tutti gli elementi nidificati.

Se usiamo solo foldl, l'effetto è ancora più bello: Siamo in grado di sollevare più volte, come in

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

Answer 3

In realtà, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs).

Anche se f è un'operazione associativa, la corretta sequenza di applicazioni questioni, in quanto può avere un impatto sulle prestazioni.

Cominciamo con

(foldl.foldr) f z xs 
foldl (foldr f) z xs 

scrivere con g = foldr f e [x1,x2,...,xn_1,xn] = xs per un momento, questo è

(...((z `g` x1) `g` x2) ... `g` xn) 
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ...) 
foldr f z $ concat [xn,xn_1, ..., x1] 
foldr f z $ concat $ reverse xs 

Quindi nel tuo caso la sequenza di riduzione corretta

(foldl.foldr) 1 [[1,2,3],[4,5,6]] 
4+(5+(6+( 1+(2+(3+ 1))))) 
22 

Vale a dire ,

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]] 
[7,8,4,5,6,1,2,3] 

---

Analogamente, (foldl.foldl) f z xs == foldl f z $ concat xs. Con snoc a b = a++[b],

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]] 
[1,2,3,4,5,6,7,8] 

Inoltre, (foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs), ecc .:

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[1,2,3,4,5,6,7,8] 
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,1,2,3,4,5,6] 
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]] 
[7,8,4,5,6,1,2,3]