liste Chiesa in Haskell

Question

ho dovuto implementare la funzione Haskell mappa per lavorare con gli elenchi delle chiese che sono definiti come segue:

type Churchlist t u = (t->u->u)->u->u 

In lambda calcolo, le liste sono codificati come segue:

[] := λc. λn. n 
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n)) 

la soluzione campione di questo esercizio è:

mapChurch :: (t->s) -> (Churchlist t u) -> (Churchlist s u) 
mapChurch f l = \c n -> l (c.f) n 

ho idea di come funziona questa soluzione e io don' so come creare una tale funzione. Ho già esperienza con calcolo lambda e numeri di chiesa, ma questo esercizio è stato un grosso problema per me e devo essere in grado di capire e risolvere questi problemi per il mio esame la prossima settimana. Qualcuno potrebbe darmi una buona fonte per imparare a risolvere questi problemi o darmi una piccola guida su come funziona?

Answer 1

Tutte le strutture di dati del calcolo lambda sono, beh, funzioni, perché questo è tutto ciò che c'è nel calcolo lambda. Ciò significa che la rappresentazione di un booleano, di una tupla, di un elenco, di un numero o di qualcosa deve essere una funzione che rappresenta il comportamento attivo di quella cosa.

Per gli elenchi, è una "piegatura". Le liste immutabili single-linked sono in genere definite List a = Cons a (List a) | Nil, il che significa che l'unico modo in cui è possibile creare un elenco è Nil o Cons anElement anotherList.Se si scrive fuori in Lisp-stile, dove c è Cons e n è Nil, allora la lista [1,2,3] si presenta così:

(c 1 (c 2 (c 3 n))) 

Quando si esegue una piega su una lista, è sufficiente fornire il proprio "Cons "e" Nil "per sostituire quelli della lista. In Haskell, la funzione di libreria per questo è foldr

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

sembra familiare? Estrai lo [a] e hai esattamente lo stesso tipo di Churchlist a b. Come ho detto, la codifica della chiesa rappresenta le liste come funzione di piegatura.

---

Quindi l'esempio definisce map. Si noti come l viene utilizzato come funzione: è la funzione che si ripiega su qualche elenco, dopo tutto. \c n -> l (c.f) n in pratica dice "sostituisci ogni c con c . f e ogni n con n".

(c 1 (c 2 (c 3 n))) 
-- replace `c` with `(c . f)`, and `n` with `n` 
((c . f) 1 ((c . f) 2) ((c . f) 3 n))) 
-- simplify `(foo . bar) baz` to `foo (bar baz)` 
(c (f 1) (c (f 2) (c (f 3) n)) 

Dovrebbe essere evidente ora che questa è davvero una funzione di mappatura, perché sembra proprio come l'originale, ad eccezione 1 trasformato in (f 1), 2-(f 2), e 3-.

Answer 2

Quindi partiamo codificando i due costruttori della lista, utilizzando il vostro esempio come riferimento:

[] := λc. λn. n 
[1,2,3] := λc. λn. c 1 (c 2 (c 3 n)) 

[] è la fine della lista del costruttore, e siamo in grado di sollevare quel dritto dall'esempio. [] ha già un significato in Haskell, quindi cerchiamo di chiamare il nostro nil:

nil = \c n -> n 

L'altro costruttore dobbiamo prende un elemento e un elenco esistente, e crea un nuovo elenco. Canonicamente, questo si chiama cons, con la definizione:

cons x xs = \c n -> c x (xs c n) 

Possiamo controllare che questo sia coerente con l'esempio di cui sopra, in quanto

cons 1 (cons 2 (cons 3 nil))) = 
cons 1 (cons 2 (cons 3 (\c n -> n)) = 
cons 1 (cons 2 (\c n -> c 3 ((\c' n' -> n') c n))) = 
cons 1 (cons 2 (\c n -> c 3 n)) = 
cons 1 (\c n -> c 2 ((\c' n' -> c' 3 n') c n)) = 
cons 1 (\c n -> c 2 (c 3 n)) = 
\c n -> c 1 ((\c' n' -> c' 2 (c' 3 n')) c n) = 
\c n -> c 1 (c 2 (c 3 n)) = 

Ora, prendere in considerazione lo scopo della funzione di carta - è per applicare la funzione data a ciascun elemento della lista. Quindi vediamo come funziona per ciascuno dei costruttori.

nil ha alcun elementi, così mapChurch f nil dovrebbe essere solo nil:

mapChurch f nil 
= \c n -> nil (c.f) n 
= \c n -> (\c' n' -> n') (c.f) n 
= \c n -> n 
= nil 

cons presenta un elemento e un resto di lista, quindi, affinché mapChurch f per lavorare propery, deve applicare f all'elemento e mapChurch f al resto della lista. Cioè, mapChurch f (cons x xs) dovrebbe essere lo stesso di cons (f x) (mapChurch f xs).

mapChurch f (cons x xs) 
= \c n -> (cons x xs) (c.f) n 
= \c n -> (\c' n' -> c' x (xs c' n')) (c.f) n 
= \c n -> (c.f) x (xs (c.f) n) 
-- (c.f) x = c (f x) by definition of (.) 
= \c n -> c (f x) (xs (c.f) n) 
= \c n -> c (f x) ((\c' n' -> xs (c'.f) n') c n) 
= \c n -> c (f x) ((mapChurch f xs) c n) 
= cons (f x) (mapChurch f xs) 

Quindi, dal momento tutte le liste sono fatte da quei due costruttori, e mapChurch lavori su entrambi come previsto, mapChurch devono lavorare come previsto in tutte le liste.

Answer 3

Beh, siamo in grado di commentare il tipo Churchlist in questo modo per chiarire che:

-- Tell me... 
type Churchlist t u = (t -> u -> u) -- ...how to handle a pair 
        -> u   -- ...and how to handle an empty list 
        -> u   -- ...and then I'll transform a list into 
            -- the type you want 

Si noti che questo è intimamente legata alla funzione foldr:

foldr :: (t -> u -> u) -> u -> [t] -> u 
foldr k z [] = z 
foldr k z (x:xs) = k x (foldr k z xs) 

foldr è una funzione molto generale che può implementare ogni sorta di altre funzioni di lista. Un esempio banale che vi aiuterà sta attuando una copia elenco con foldr:

copyList :: [t] -> [t] 
copyList xs = foldr (:) [] xs 

Uso del tipo sopra commentata, foldr (:) [] significa questo: "se vedi un elenco vuoto restituisce la lista vuota, e se si vede una coppia restituire head:tailResult. "

Utilizzando Churchlist, si può facilmente scrivere la controparte in questo modo:

-- Note that the definitions of nil and cons mirror the two foldr equations! 
nil :: Churchlist t u 
nil = \k z -> z 

cons :: t -> Churchlist t u -> Churchlist t u 
cons x xs = \k z -> k x (xs k z) 

copyChurchlist :: ChurchList t u -> Churchlist t u 
copyChurchlist xs = xs cons nil 

Ora, per implementare map, basta sostituire cons con una opportuna funzione, in questo modo:

map :: (a -> b) -> [a] -> [b] 
map f xs = foldr (\x xs' -> f x:xs') [] xs 

La mappatura è come copiare un elenco, tranne per il fatto che anziché copiare semplicemente gli elementi alla lettera si applica f a ciascuno di essi.

Studia tutto con attenzione, e dovresti essere in grado di scrivere mapChurchlist :: (t -> t') -> Churchlist t u -> Churchlist t' u da solo.

esercizio supplementare (facile): scrivere queste funzioni lista in termini di foldr, e scrivere le controparti per Churchlist:

filter :: (a -> Bool) -> [a] -> [a] 
append :: [a] -> [a] -> [a] 

-- Return first element of list that satisfies predicate, or Nothing 
find :: (a -> Bool) -> [a] -> Maybe a 

Se ti senti come affrontare qualcosa di più difficile, provare a scrivere tail per Churchlist. (Inizia scrivendo tail per [a] utilizzando foldr.)