Usando foldr per aggiungere due liste insieme (Haskell)

Gli elenchi di piegature sono composti da tre elementi: l'elenco da piegare, una funzione di accumulatore f e un valore iniziale.

Trasformano la lista a:b:c:[] in (a f (b f (c f init))) dove init è l'elemento iniziale, ovvero sostituiscono il costruttore cons : con la funzione accumulatore e la lista vuota [] con il valore iniziale fornito.

Puoi pensare alla tua funzione append come trasformare la lista x1:x2:..:xn nella lista x1:x2:..:xn:ys per un dato elenco ys . Questo può essere fatto semplicemente usando ys come sostituto per la lista vuota [] che termina la tua lista xs .

Il tuo codice può essere scritto come

append xs ys = foldr (\x y -> x:y) ys xs

La tua funzione accumulatore f ha il tipo a -> [a] -> [a] ed è uguale alla funzione (:) , quindi potresti scriverlo come

append xs ys = foldr (:) ys xs

Se il primo argomento xs è la lista x1: x2: ...: xn allora il risultato di append è la lista x1:x2:...xn:ys come richiesto.

Per prima cosa, semplifichiamo la tua soluzione un po 'con Haskell standard per renderlo più facile da comprendere:

append = \xs -> \ys -> foldr (\x -> \y -> x:y) ys xs

può essere scritto come

append xs ys = foldr (:) ys xs

perché \x -> \y -> x : y equivale a \x -> y -> (:) x y che equivale a (:) (questo è chiamato riduzione η , qui l'abbiamo applicata due volte).

Suppongo tu sappia come funziona foldr quindi diamo un'occhiata a questo caso speciale: Qui foldr è specializzato per digitare (a -> [a] -> [a]) -> [a] -> [a] -> [a] . Il valore accumulato durante la piegatura è di tipo [a] , lo stesso tipo della lista che stiamo consumando. (Questo è probabilmente ciò che rende questo un po 'confuso.) Iniziamo con ys come valore accumulato. Quindi foldr elabora elementi di xs da destra a sinistra e ad ogni passo antepone (usando : ) l'elemento attualmente ispezionato al valore accumulato al momento. Quindi inizia anteponendo l'ultimo elemento di xs davanti a ys , quindi il penultimo elemento di xs a quello ecc., Infine costruendo l'intero xs anteposto a ys .

(Come altro esercizio per comprendere le pieghe, ti suggerisco di provare a implementare foldl usando solo foldr . Passa il mouse sopra l'area seguente per un suggerimento.)

The accumulated/returned value produced by foldr needs to be a function.

append :: [a] - > [a] - > [A]

append = flip (foldr (:))

Cerco di spiegare foldr:

Quando usiamo foldr (:) [1,2,3] [4,5,6] senza il flip

prendiamo il secondo argomento che è [4,5,6] l'ultimo elemento dell'argomento è 6, che applichiamo con (:) al nostro primo argomento [1,2,3] che ci darà poi [6,1,2,3].

L'ultimo elemento successivo è 5, su cui faremo la stessa operazione, che ci dà [5,6,1,2,3].

Infine finiamo con [4,5,6,1,2,3], che non è l'ordine giusto solo se scambiamo la posizione degli argomenti [1,2,3] con [4,5,6] questo lo facciamo usando flip (foldr (:)), che ci darà il giusto ordine di argomenti

e risultati in [1,2,3,4,5,6]