Come è ovvio che (foldr Cons Nil) copia solo una lista?

Question

Come è ovvio che (foldr Cons Nil) copia solo una lista?

#1 da (5 voti)
#2 da (0 voti)

1

Attualmente sto leggendo Perché la programmazione funzionale è importante di John Hughes .

Nella sezione "Gluing Functions Together", dopo aver spiegato che (foldr f a) è una funzione che sostituisce tutte le occorrenze di Cons in un elenco di f e tutte le occorrenze di Nil di a ( che capisco), l'autore scrive: "Ora è ovvio che (foldr Cons Nil) copia solo un elenco" e fornisce questo esempio per illustrare il punto:

append [1, 2] [3, 4] = foldr Cons [3, 4] [1, 2]
                     = foldr Cons [3, 4] (Cons 1 (Cons 2 Nil))
                     = Cons 1 (Cons 2 [3, 4]))
                     = [1, 2, 3, 4]

Non capisco perché nella terza riga dell'esempio dato, (Cons 1 (Cons 2 Nil)) è improvvisamente in primo piano e di conseguenza perché l'elenco non finisce per essere [3, 4, 1, 2] . Nil in (Cons 1 (Cons 2 Nil)) a ed è Cons [3, 4] f se foldr la definizione è foldr f a ?

In che modo è ovvio che foldr Cons Nil copia solo un elenco?

functional-programming haskell

posta nich 25.07.2017 - 23:03

fonte

2 risposte

5

Sostituire Cons di Cons e Nil di Nil mantiene le cose uguali!

Nell'esempio append , [3, 4] è ciò che sostituisce Nil .

risposta data 26.07.2017 - 00:04

fonte

Leggi altre domande sui tag functional-programming haskell

Tutti i metodi di database dovrebbero essere nel repository? Che cos'è una "app di streaming", esattamente?

score 0 · Accepted Answer

Dobbiamo sostituire 3 volte per passare dalla linea 2 alla linea 3. Utilizzando la definizione di foldr fornita a pagina 5:

(foldr f x) Nil = x
(foldr f x) (Cons a l) = f a ((foldr f x) l)

prendendo la seconda riga dell'esempio dato, e sostituendo la seconda riga del foldr defn, scriverò la variabile corrispondente sotto ogni argomento:

                 = foldr Cons [3, 4] (Cons 1 (Cons 2 Nil))
defn:             (foldr  f     x)   (Cons a      l   )     = f a ((foldr f x) l)

gives:             Cons 1 ((foldr Cons [3,4]) (Cons 2 Nil) )

sostituendo di nuovo per questo .......... ^ occorrenza di foldr dà:

                   Cons 1 (Cons 2 ((foldr Cons [3,4] Nil)

e ancora, ma questa volta prendendo la prima riga del foldr defn:

                   Cons 1 (Cons 2 (Cons [3,4])