Vi portiamo la risposta a questa battuta d'arresto, almeno così pensiamo. Se hai domande, faccelo sapere in un commento, sarà un piacere per noi aiutarti
Soluzione:
Una piega per ogni occasione
In realtà, possiamo trovare una nozione generica di piegatura che può essere applicata a un gran numero di tipi diversi. Cioè, possiamo definire sistematicamente un fold per liste, alberi e altro ancora.
Questa nozione generica di fold corrisponde ai catamorfismi citati da @pelotom nel suo commento.
Tipi ricorsivi
L'intuizione chiave è che questi fold sono definite su ricorsivo tipi. In particolare:
data List a = Cons a (List a) | Nil
data Tree a = Branch (Tree a) (Tree a) | Leaf a
Entrambi questi tipi sono chiaramente ricorsivi.List nel Cons e Tree nel caso Branch caso.
Punti fissi
Proprio come le funzioni, possiamo riscrivere questi tipi utilizzando i punti fissi. Ricordate la definizione di fix:
fix f = f (fix f)
Possiamo scrivere qualcosa di molto simile per i tipi, tranne che per il fatto che devono avere un costruttore aggiuntivo:
newtype Fix f = Roll (f (Fix f))
Proprio come fix definisce il punto fisso di un oggetto funzione, questo definisce il punto fisso di una funzione funtore. Possiamo esprimere tutti i nostri tipi ricorsivi usando questo nuovo Fix tipo.
Questo ci permette di riscrivere List come segue:
data ListContainer a rest = Cons a rest | Nil
type List a = Fix (ListContainer a)
Essenzialmente, Fix ci permette di annidare ListContainera profondità arbitrarie. Quindi potremmo avere:
Roll Nil
Roll (Cons 1 (Roll Nil))
Roll (Cons 1 (Roll (Cons 2 (Roll Nil))))
che corrispondono a [], [1] e [1,2] rispettivamente.
Vedendo che ListContainer è un Functor è facile:
instance Functor (ListContainer a) where
fmap f (Cons a rest) = Cons a (f rest)
fmap f Nil = Nil
Penso che la mappatura da ListContainer a List è abbastanza naturale: invece di ricorrervi esplicitamente, rendiamo la parte ricorsiva una variabile. Poi usiamo semplicemente Fix per riempire la variabile nel modo più appropriato.
Possiamo scrivere un tipo analogo per Tree anche.
"Sbrogliare" i punti fissi
Perché ci interessa? Possiamo definire fold per arbitrario scritti utilizzando Fix. In particolare:
fold :: Functor f => (f a -> a) -> (Fix f -> a)
fold h = h . fmap (fold h) . unRoll
where unRoll (Roll a) = a
In sostanza, una piega non fa altro che srotolare il tipo "arrotolato" un livello alla volta, applicando ogni volta una funzione al risultato. Questo "srotolamento" ci permette di definire una piega per qualsiasi tipo ricorsivo e di generalizzare in modo ordinato e naturale il concetto.
Per l'esempio dell'elenco, funziona così:
- A ogni passo, srotoliamo l'elemento
Rollper ottenere un elementoConso unNil - Ricorriamo al resto dell'elenco usando
fmap.- Nel
Nilè il caso di,fmap (fold h) Nil = Nil, quindi restituiamo semplicementeNil. - Nel caso
Consil valorefmapcontinua la piega sul resto dell'elenco.
- Nel
- Alla fine, otteniamo un gruppo di chiamate annidate a
foldche terminano con unNil--proprio come lo standardfoldr.
Tipi a confronto
Esaminiamo ora i tipi delle due funzioni di piegatura. Primo, foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
Ora, fold si è specializzato in ListContainer:
fold :: (ListContainer a b -> b) -> (Fix (ListContainer a) -> b)
All'inizio sembrano completamente diversi. Tuttavia, con un po' di massaggio, possiamo dimostrare che sono uguali. I primi due argomenti di foldr sono a -> b -> b e b. Abbiamo una funzione e una costante. Possiamo pensare a b come () -> b. Ora abbiamo due funzioni _ -> b dove _ è () e a -> b. Per semplificare la vita, arricchiamo la seconda funzione che ci dà (a, b) -> b. Ora possiamo scriverli come un singolo utilizzando la funzione Either:
Either (a, b) () -> b
Questo è vero perché dato f :: a -> c e g :: b -> cpossiamo sempre scrivere quanto segue:
h :: Either a b -> c
h (Left a) = f a
h (Right b) = g b
Quindi ora possiamo vedere foldr come:
foldr :: (Either (a, b) () -> b) -> ([a] -> b)
(Siamo sempre liberi di aggiungere parentesi intorno a -> in questo modo, purché siano di tipo associativo).
Ora guardiamo ListContainer. Questo tipo ha due casi: Nilche non contiene informazioni e Cons, che ha sia un a e un b. In altre parole, Nil è come () e Cons è come (a, b), quindi possiamo scrivere:
type ListContainer a rest = Either (a, rest) ()
Chiaramente questo è lo stesso che ho usato in foldr sopra. Quindi ora abbiamo:
foldr :: (Either (a, b) () -> b) -> ([a] -> b)
fold :: (Either (a, b) () -> b) -> (List a -> b)
Quindi, in effetti, i tipi sono isomorfi: solo modi diversi di scrivere la stessa cosa! Penso che sia molto bello.
(Come nota a margine, se volete saperne di più su questo tipo di ragionamento con i tipi, date un'occhiata a The Algebra of Algebraic Data Types, una bella serie di post sul blog che tratta proprio questo argomento).
Ritorno agli alberi
Abbiamo visto come si possa definire un generico albero di tipo fold per i tipi scritti come punti fissi. Abbiamo anche visto come questo corrisponda direttamente a foldr per le liste. Vediamo ora il secondo esempio, l'albero binario. Abbiamo il tipo
data Tree a = Branch a (Tree a) (Tree a) | Leaf a
possiamo riscriverlo usando Fix seguendo le regole di cui sopra: sostituiamo la parte ricorsiva con una variabile di tipo:
data TreeContainer a rest = Branch rest rest | Leaf a
type Tree a = Fix (TreeContainer a)
Ora abbiamo un albero fold:
fold :: (TreeContainer a b -> b) -> (Tree a -> b)
Il vostro originale foldTree ha questo aspetto:
foldTree :: (b -> b -> b) -> (a -> b) -> Tree a -> b
foldTree accetta due funzioni; le combineremo in una sola facendo prima un curry e poi usando Either:
foldTree :: (Either (b, b) a -> b) -> (Tree a -> b)
Possiamo anche vedere come Either (b, b) a sia isomorfo a TreeContainer a b. Il contenitore ad albero ha due casi: Branch, contenente due be Leaf, contenente un a.
Quindi questi tipi di pieghe sono isomorfi come nell'esempio dell'elenco.
Generalizzazione
Emerge un chiaro schema. Dato un normale tipo di dati ricorsivo, possiamo creare sistematicamente una versione non ricorsiva del tipo, che ci permette di esprimere il tipo come punto fisso di un funtore. Ciò significa che possiamo ottenere meccanicamente fold per tutti questi tipi diversi, anzi, probabilmente potremmo automatizzare l'intero processo usando GHC Generics o qualcosa di simile.
In un certo senso, questo significa che non abbiamo diversi tipi di funzioni fold per tipi diversi. Piuttosto, abbiamo una singola funzione fold che è molto polimorfica.
Di più
Ho compreso appieno queste idee grazie a un discorso tenuto da Conal Elliott. Questo discorso è più dettagliato e parla anche di unfoldche è il duale di fold.
Se si vuole approfondire questo genere di cose anche di più profondamente, leggete il fantastico articolo "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire". Tra le altre cose, introduce le nozioni di "catamorfismi" e "anamorfismi", che corrispondono a pieghe e dispiegamenti.
Algebre (e algebre del carbone)
Inoltre, non posso resistere all'idea di aggiungere una spina per me stesso :P. Si possono notare alcune interessanti somiglianze tra il modo in cui usiamo Either qui e il modo in cui l'ho usato quando ho parlato di algebre in un'altra risposta del SO.
C'è infatti una profonda connessione tra fold e le algebre; inoltre, unfold-il già citato duale di fold--è collegato alle coalgebre, che sono il duale delle algebre. L'idea importante è che i tipi di dati algebrici corrispondono ad "algebre iniziali" che definiscono anche le pieghe, come illustrato nel resto della mia risposta.
Si può vedere questa connessione nel tipo generale di fold:
fold :: Functor f => (f a -> a) -> (Fix f -> a)
Il f a -> a ha un aspetto molto familiare! Ricordate che un'algebra f è stata definita come qualcosa di simile:
class Functor f => Algebra f a where
op :: f a -> a
Quindi possiamo pensare a fold come semplicemente:
fold :: Algebra f a => Fix f -> a
Essenzialmente, fold ci permette di "riassumere" le strutture definite utilizzando l'algebra.
Tikhon ha fatto la parte tecnica. Credo che cercherò di semplificare quello che ha detto.
Il termine "folding", purtroppo, è diventato ambiguo nel corso degli anni per indicare una delle due cose:
- Ridurre un insieme in modo sequenziale in un certo ordine. In Haskell, questo è il significato di "ripiegamento" nella classe di testo
Foldabledi cui parla larsmans. - La nozione che avete chiesto: "distruggere" (opposto di costruire), "osservare" o "eliminare" un tipo di dato algebrico in base alla sua struttura. Chiamato anche catamorfismo.
È possibile definire entrambe le nozioni in modo generico, in modo che una funzione parametrizzata sia in grado di farlo per una varietà di tipi. Tichon mostra come fare nel secondo caso.
Ma il più delle volte si va fino in fondo con Fix e le algebre e così via è eccessivo. Vediamo un modo più semplice di scrivere la piega per qualsiasi tipo di dato algebrico. Utilizzeremo Maybe, coppie, liste e alberi come esempi:
data Maybe a = Nothing | Just a
data Pair a b = Pair a b
data List a = Nil | Cons a (List a)
data Tree x = Leaf x | Branch (Tree x) (Tree x)
data BTree a = Empty | Node a (BTree a) (BTree a)
Si noti che Pair non è ricorsivoe; La procedura che sto per mostrare non presuppone che il tipo di "piega" sia ricorsivo. Di solito non si chiama questo caso "piega", ma in realtà è il caso non ricorsivo dello stesso concetto.
Primo passo: la piegatura per un dato tipo consumerà il tipo piegato e produrrà un tipo di parametro come risultato. Mi piace chiamare quest'ultimo r (per "risultato"). Quindi:
foldMaybe :: ... -> Maybe a -> r
foldPair :: ... -> Pair a b -> r
foldList :: ... -> List a -> r
foldTree :: ... -> Tree a -> r
foldBTree :: ... -> BTree a -> r
Secondo passo: oltre all'ultimo argomento (quello per la struttura), la piega prende tanti argomenti quanti sono i costruttori del tipo. Pair ha un solo costruttore e gli altri esempi ne hanno due, quindi:
foldMaybe :: nothing -> just -> Maybe a -> r
foldPair :: pair -> Pair a b -> r
foldList :: nil -> cons -> List a -> r
foldTree :: leaf -> branch -> Tree a -> r
foldBTree :: empty -> node -> BTree a -> r
Terzo passo: ognuno di questi argomenti ha la stessa arità del costruttore a cui corrisponde. Trattiamo i costruttori come funzioni e scriviamo i loro tipi (assicurandoci che le variabili di tipo corrispondano a quelle delle firme che stiamo scrivendo):
Nothing :: Maybe a
Just :: a -> Maybe a
Pair :: a -> b -> Pair a b
Nil :: List a
Cons :: a -> List a -> List a
Leaf :: a -> Tree a
Branch :: Tree a -> Tree a -> Tree a
Empty :: BTree a
Node :: a -> BTree a -> BTree a -> BTree a
Passo 4: nella firma di ogni costruttore, sostituiremo tutte le occorrenze del tipo di dati che costruisce con la nostra variabile di tipo r (che stiamo usando nelle firme delle nostre pieghe):
nothing := r
just := a -> r
pair := a -> b -> r
nil := r
cons := a -> r -> r
leaf := a -> r
branch := r -> r -> r
empty := r
node := a -> r -> r -> r
Come si può vedere, ho "assegnato" le firme risultanti alle mie variabili di tipo fittizio del secondo passo. Ora passo 5: inserirle nelle firme delle pieghe dello schizzo precedente:
foldMaybe :: r -> (a -> r) -> Maybe a -> r
foldPair :: (a -> b -> r) -> Pair a b -> r
foldList :: r -> (a -> r -> r) -> List a -> r
foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r
foldBTree :: r -> (a -> r -> r -> r) -> BTree a -> r
Queste sono le firme per le pieghe di questi tipi. Hanno uno strano ordine degli argomenti, perché l'ho fatto meccanicamente leggendo il tipo di piega dalla variabile data e dai tipi di costruttore, ma per qualche ragione nella programmazione funzionale è convenzionale mettere i casi base per primi in data ma i gestori di casi ricorsivi prima in fold e i gestori di casi ricorsivi nelle definizioni fold. Nessun problema! Rimpastiamoli per renderli più convenzionali:
foldMaybe :: (a -> r) -> r -> Maybe a -> r
foldPair :: (a -> b -> r) -> Pair a b -> r
foldList :: (a -> r -> r) -> r -> List a -> r
foldTree :: (r -> r -> r) -> (a -> r) -> Tree a -> r
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
Le definizioni possono essere compilate anche meccanicamente. Scegliamo foldBTree e implementiamola passo dopo passo. La piegatura per un dato tipo è l'unica funzione del tipo che abbiamo individuato e che soddisfa questa condizione: la piegatura con i costruttori del tipo è una funzione identità su quel tipo (si ottiene lo stesso risultato del valore con cui si è iniziato).
Inizieremo così:
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree = ???
Sappiamo che accetta tre argomenti, quindi possiamo aggiungere delle variabili che li riflettano. Utilizzerò nomi lunghi e descrittivi:
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty tree = ???
Guardando il file data sappiamo che BTree ha due possibili costruttori. Possiamo dividere la definizione in un caso per ciascuno di essi e compilare le variabili per i loro elementi:
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = ???
foldBTree branch empty (Branch a l r) = ???
-- Let's use comments to keep track of the types:
-- a :: a
-- l, r :: BTree a
Ora, in mancanza di qualcosa come undefinedl'unico modo per compilare la prima equazione è con empty:
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = ???
-- a :: a
-- l, r :: BTree a
Come riempire la seconda equazione? Anche in questo caso, a meno di undefinedabbiamo questo:
branch :: a -> r -> r -> r
a :: a
l, r :: BTree a
Se avessimo subfold :: BTree a -> r, potremmo fare branch a (subfold l) (subfold r) :: r. Ma naturalmente possiamo scrivere facilmente 'subfold':
foldBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
foldBTree branch empty Empty = empty
foldBTree branch empty (Branch a l r) = branch a (subfold l) (subfold r)
where subfold = foldBTree branch empty
Questa è la piega per BTree, perché foldBTree Branch Empty anyTree == anyTree. Si noti che foldBTree non è l'unica funzione di questo tipoe; c'è anche questa:
mangleBTree :: (a -> r -> r -> r) -> r -> BTree a -> r
mangleBTree branch empty Empty = empty
mangleBTree branch empty (Branch a l r) = branch a (submangle r) (submangle l)
where submangle = mangleBTree branch empty
Ma in generale, mangleBTree non ha la proprietà richiesta; per esempio se abbiamo foo = Branch 1 (Branch 2 Empty Empty) Empty, ne consegue che mangleBTree Branch Empty foo /= foo. Quindi mangleBTree, pur avendo il tipo corretto, non è la piega.
Ora, facciamo un passo indietro rispetto ai dettagli e concentriamoci su quest'ultimo punto con l'elemento mangleTree esempio. Una piega (nel senso strutturale, #2 in cima alla mia risposta) non è altro che la più semplice funzione non banale per un tipo algebrico tale che, quando si passano i costruttori del tipo come argomenti, diventa la funzione identità per quel tipo. (Per non banale intendo che cose come foo f z xs = xs non è consentita).
Questo è molto significativo. Due modi in cui mi piace pensarci sono i seguenti:
- La piega per un dato tipo può "vedere" tutte le informazioni contenute in qualsiasi valore di quel tipo. (Questo è il motivo per cui è in grado di "ricostruire" perfettamente qualsiasi valore di quel tipo dalle fondamenta usando i costruttori del tipo).
- La piega è la funzione più generale di "consumo" di quel tipo. Ogni funzione che consuma un valore del tipo in questione può essere scritta in modo che le uniche operazioni che utilizza da quel tipo siano la piega e i costruttori. (Anche se le versioni solo pieghevoli di alcune funzioni sono difficili da scrivere e funzionano male; provate a scrivere
tail :: [a] -> [a]confoldr,(:)e[]come esercizio doloroso).
E il secondo punto va ancora oltre, nel senso che non c'è nemmeno bisogno dei costruttori. Si può implementare qualsiasi tipo algebrico senza usare data dichiarazioni o costruttori, usando solo le pieghe:
{-# LANGUAGE RankNTypes #-}
-- | A Church-encoded list is a function that takes the two 'foldr' arguments
-- and produces a result from them.
newtype ChurchList a =
ChurchList { runList :: forall r.
(a -> r -> r) -- ^ first arg of 'foldr'
-> r -- ^ second arg of 'foldr'
-> r -- ^ 'foldr' result
}
-- | Convenience function: make a ChurchList out of a regular list
toChurchList :: [a] -> ChurchList a
toChurchList xs = ChurchList (kons knil -> foldr kons knil xs)
-- | 'toChurchList' isn't actually needed, however, we can make do without '[]'
-- completely.
cons :: a -> ChurchList a -> ChurchList a
cons x xs = ChurchList (f z -> f x (runlist xs f z))
nil :: ChurchList a
nil = ChurchList (f z -> z)
foldr' :: (a -> r -> r) -> r -> ChurchList a -> r
foldr' f z xs = runList xs f z
head :: ChurchList a -> Maybe a
head = foldr' ((Just .) . const) Nothing
append :: ChurchList a -> ChurchList a -> ChurchList a
append xs ys = foldr' cons ys xs
-- | Convert a 'ChurchList' to a regular list.
fromChurchList :: ChurchList a -> [a]
fromChurchList xs = runList xs (:) []
Come esercizio, si può provare a scrivere altri tipi in questo modo (che utilizza l'elemento RankNTypes per un'esercitazione). Questa tecnica è chiamata codifica Church ed è talvolta utile nella programmazione vera e propria: ad esempio, GHC usa qualcosa chiamato foldr/build per ottimizzare il codice degli elenchi e rimuovere gli elenchi intermedi; si veda questa pagina di Haskell Wiki, e si noti il tipo di build:
build :: (forall b. (a -> b -> b) -> b -> b) -> [a]
build g = g (:) []
Fatta eccezione per l'elemento newtype, questo è lo stesso del mio fromChurchList di cui sopra. In pratica, una delle regole che GHC usa per ottimizzare il codice di elaborazione delle liste è questa:
-- Don't materialize the list if all we're going to do with it is
-- fold it right away:
foldr kons knil (fromChurchList xs) ==> runChurchList xs kons knil
Implementando le funzioni di base delle liste in modo che utilizzino internamente le codifiche di Church, inlining delle loro definizioni in modo aggressivo e applicando questa regola al codice inlining, gli usi annidati delle funzioni come map possono essere fusi in un ciclo stretto.
Un fold sostituisce ogni costruttore con una funzione.
Per esempio, foldr cons nil sostituisce ogni (:) con cons e [] con nil:
foldr cons nil ((:) 1 ((:) 2 [])) = cons 1 (cons 2 nil)
Per un albero, foldTree branch leaf sostituisce ogni Branch con branch e ogni Leaf con leaf:
foldTree branch leaf (Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3))
= branch (branch (leaf 1) (leaf 2)) (leaf 2)
Questo è il motivo per cui ogni piega accetta argomenti dello stesso tipo dei costruttori:
foldr :: (a -> list -> list) -> list -> [a] -> list
foldTree :: (tree -> tree -> tree) -> (a -> tree) -> Tree a -> tree
Ti mostriamo recensioni e valutazioni
Apprezziamo che tu voglia supportare il nostro compito pubblicando un commento e valutandolo, ti diamo il benvenuto.