Funzioni specifiche di ordine superiore con foldr e foldl

Question

Non riesco a interpretare la firma della funzione per foldl. Capisco come funziona, ma non sono sicuro di come si riferisce alla firma.

ho alcune domande sulla sua dettaglio

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

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

Sembra che il primo parametro assume una funzione aggiunta:

(a -> b -> b) 

All'interno l'argomento della funzione, cosa sta succedendo? Questa sezione applica il numero intero più a destra a all'accumulatore b per ottenere un altro numero intero 9 in questo caso? Dopodiché, restituisce una funzione che accetta l'accumulatore come parametro?

E in seguito, cosa significano gli ultimi due parametri seguenti?

[a] -> b 

Molte grazie.

Answer 1

Quando si passa (+) per il primo argomento di foldr implicitamente dichiara che a è lo stesso di b. Questo diventa confusa perché si tende a riutilizzare i nomi, ma se scrivo tutto insieme utilizzando lo stesso spazio dei nomi per le variabili di tipo

(+)  :: Num i => i -> i -> i 
foldr  :: (a -> b -> b) -> b -> [a] -> b 
foldr (+) :: Num i => i -> [i] -> i 

dove la terza linea implica che i ~ a e i ~ b quindi, per transitività, a ~ b. Inoltre, potrebbe essere più chiaro qui per vedere che il primo parametro rimanente in foldr (+) è un valore "iniziale" per la piega e il bit [i] è l'elenco che stiamo comprimendo, piegando, riducendo.

Potrebbe essere ancora più chiaro chiamare foldr (+) 0 tramite il nome più comune, sum :: Num a => [a] -> a. Abbiamo anche foldr (*) 1 come product :: Num a => a -> [a].

Quindi sì, la descrizione di come si sta comportando la funzione di accumulatore in foldr (+) è esattamente corretta, ma più specifica della funzione è in generale. Ad esempio, possiamo utilizzare foldr per creare un Map.

foldr (\(k, v) m -> Map.insert m k v) Map.empty :: Ord k => [(k, v)] -> Map k v 

In questo caso la funzione accumulatore prende nostra lista associazione e mantiene inserendo i valori nel nostro accumulat * * ing Map, che inizia vuoto. Per essere del tutto accurato qui, mi permetta di scrivere i tipi di nuovo tutti insieme

(\(k, v) -> m -> Map.insert m k v)  :: Ord k => (k, v) -> Map k v -> Map k v 
foldr         :: (a -> b -> b) -> b -> [a] -> b 
foldr (\(k, v) -> m -> Map.insert m k v) :: Ord k => Map k v -> [(k, v)] -> Map k v 

dove siamo costretti a ~ (k, v) e b ~ Map k v.

---

Come un parere definitivo sulla questione, ecco la definizione di foldr con alcuni nomi di variabili suggestivi

foldr _ b []  = b 
foldr (<>) b (a:as) = a <> foldr f b as 

Così si può vedere come (<>) :: a -> b -> b combina a e b tipi. Possiamo "eseguire" esplicitamente questa definizione per vedere come si costruisce il calcolo.

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

Quale può essere ancora più chiaro quando si usa un'operazione non simmetrica come il Map esempio di cui sopra. Qui di seguito sto usando {{ k -> v, k -> v }} per rappresentare lo Map poiché non è stampabile direttamente.

-- inserts a single (k,v) pair into a Map 
ins :: Ord k => (k, v) -> Map k v -> Map k v 
ins (k, v) m = Map.insert m k v 

foldr ins Map.empty [('a', 1), ('b', 2)] 
ins ('a', 1) (foldr ins Map.empty [('b', 2)]) 
ins ('a', 1) (ins ('b', 2) (foldr ins Map.empty [])) 
ins ('a', 1) (ins ('b', 2) Map.empty) 
ins ('a', 1) (ins ('b', 2) {{ }}) 
ins ('a', 1) {{ 'b' -> 2 }} 
{{ 'b' -> 2, 'a' -> 1 }} 

Answer 2

Dipende da come lo si guarda. Il primo passaggio produce (+) 1 (foldr (+) 5 [2,3,4]). Mentre provate ad usare il risultato del folding, questo forzerà la valutazione del secondo argomento di (+), e poiché (+) è rigoroso, questo svela l'intera lista. L'ultimo passaggio produce (+) 1 ((+) 2 ((+) 3 ((+) 4 5))). Quindi, sì, i primi due numeri aggiunti sono 4 e 5, ma questa non è la prima cosa che foldr fa, e in questo caso la lista verrà sostituita con un albero di thunk prima, quindi valutarla per ottenere la somma di tutti numeri e 5.

La sostituzione dell'elenco con i thunk è buona nei casi in cui la funzione non è rigida - in questo modo è possibile valutare solo quanto necessario, anche un elenco potenzialmente infinito. Nei casi in cui la funzione è rigorosa, è opportuno prendere in considerazione la riscrittura con foldl'.

Answer 3

Ecco la firma tipo di foldr:

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

Prende una funzione (chiamata esso passo) che assume il valore successivo (a un) e il valore accumulato (a b) e produce un nuovo valore accumulato (anche b)

step :: a -> b -> b 

e un accumulat inititial o il valore (un b):

initialValue :: b 

e un elenco di ingressi per piegare (una lista di un 's):

inputs :: [a] 

E infine si ottiene un'uscita (un b)

output :: b 

Così si ottiene una forma generale:

output = foldr step initialValue inputs