Catamorphism e albero-traslazione in Haskell

Question

Sono impaziente, in attesa di catamorphism comprensione relative a questo SO domanda :)

Ho praticato solo l'inizio di Real World Haskell tutorial. Così, forse sto andando chiedere un po 'troppo in questo momento, se fosse il caso, dimmi solo i concetti dovrei imparare.

Di seguito, cito il wikipedia esempio di codice per catamorphism .

mi piacerebbe conoscere la vostra opinione su foldTree sotto, un modo di attraversare un albero, rispetto a quest'altra domanda SO e risposta, anche trattare con l'attraversamento di un albero n-ario albero attraversamento . (In modo indipendente da essere binario o no, penso che la catamorphism di seguito può essere scritto in modo tale da gestire albero n-ario)

ho messo in commento quello che ho capito, e sarò contento se potesse correggere e chiarire alcune cose.

{-this is a binary tree definition-}
data Tree a = Leaf a
            | Branch (Tree a) (Tree a)

{-I dont understand the structure between{} 
however it defines two morphisms, leaf and branch 
leaf take an a and returns an r, branch takes two r and returns an r-} 
data TreeAlgebra a r = TreeAlgebra { leaf   :: a      -> r
                                   , branch :: r -> r -> r }

{- foldTree is a morphism that takes: a TreeAlgebra for Tree a with result r, a Tree a
and returns an r -} 
foldTree :: TreeAlgebra a r -> Tree a -> r
foldTree a@(TreeAlgebra {leaf   = f}) (Leaf   x  ) = f x
foldTree a@(TreeAlgebra {branch = g}) (Branch l r) = g (foldTree a l) (foldTree a r)

a questo punto io sto avendo molte difficoltà, mi sembra di intuire che la foglia morfismo verrà applicato a qualsiasi Leaf Ma in modo da utilizzare questo codice per reale, foldTree bisogno di essere alimentato un TreeAlgebra definito, un TreeAlgebra che ha una foglia morfismo definito in modo da fare qualcosa?
ma in questo caso nel codice foldTree mi aspetterei {f = foglia} e non il contrario

Qualsiasi chiarimento da voi sarebbe davvero il benvenuto.

Answer 1

Non esattamente sicuro di quello che stai chiedendo. Ma sì, si alimenta un TreeAlgebra per foldTree corrispondente al calcolo che si desidera eseguire sul legno della croce. Ad esempio, per sommare tutti gli elementi in un albero di Ints si può usare questa algebra:

sumAlgebra :: TreeAlgebra Int Int
sumAlgebra = TreeAlgebra { leaf = id
                         , branch = (+) }

Il che significa, per ottenere la somma di una foglia, applicare id (non fare nulla) al valore nella foglia. Per ottenere la somma di un ramo, sommare i somme di ciascuno dei bambini.

Il fatto che possiamo dire (+) alla succursale, invece di, diciamo, \x y -> sumTree x + sumTree y è la proprietà essenziale del catamorphism. Si dice che per calcolare qualche funzione f su qualche struttura dati ricorsiva è sufficiente avere i valori di f per i suoi figli immediati.

Haskell è un linguaggio abbastanza unico in quanto siamo in grado di formalizzare l'idea di catamorphism astrattamente. Facciamo un tipo di dati per un singolo nodo nell'albero, parametrizzata rispetto ai suoi figli:

data TreeNode a child
    = Leaf a
    | Branch child child

vedi quello che abbiamo fatto lì? Abbiamo appena sostituito i figli ricorsive con un tipo di nostra scelta. Questo è così che possiamo mettere somme sottoalberi quando ci sono pieghevoli.

Ora, per la cosa veramente magica. Ho intenzione di scrivere questo in pseudohaskell - scriverlo in real Haskell è possibile, ma dobbiamo aggiungere alcune annotazioni per aiutare coontrollore dei tipo che può essere tipo di confusione. Prendiamo il "punto fisso" di un tipo di dati con parametri - che è, la costruzione di un tipo di dati T tale che T = TreeNode a T. Lo chiamano questo operatore Mu.

type Mu f = f (Mu f)

Guardate attentamente qui. L'argomento di Mu non è un tipo, come Int o Foo -> Bar. E 'un tipo di costruttore come Maybe o TreeNode Int - l'argomento a Mu si prende un argomento. (La possibilità di astrarre sopra costruttori di tipo è una delle cose che rende il sistema tipo di Haskell si distingua nella sua forza espressiva).

Quindi il tipo Mu f è definito come prendere f e riempimento nel suo parametro di tipo con Mu f stessa. Ho intenzione di definire un sinonimo per ridurre alcuni dei rumori:

type IntNode = TreeNode Int

L'espansione Mu IntNode, otteniamo:

Mu IntNode = IntNode (Mu IntNode)
           = Leaf Int | Branch (Mu IntNode) (Mu IntNode)

Vedete come Mu IntNode è equivalente al vostro Tree Int? Abbiamo appena strappato la struttura ricorsiva a parte e poi utilizzato Mu per mettere di nuovo insieme. Questo ci dà il vantaggio che si può parlare di tutti i tipi Mu in una sola volta. Questo ci dà quello che ci serve per definire un catamorphism.

Let definire:

type IntTree = Mu IntNode

Ho detto la proprietà essenziale del catamorphism è quello di calcolare qualche funzione f, è sufficiente avere i valori di f per i suoi figli immediati. Chiamiamo il tipo di cosa che stiamo cercando di r calcolo, e la node struttura dati (IntNode sarebbe una possibile esemplificazione di questo). Quindi, per r calcolo su un nodo particolare, abbiamo bisogno del nodo con i suoi figli sostituiti con i loro rs. Questo calcolo è di tipo node r -> r. Quindi un catamorphism dice che se abbiamo uno di questi calcoli, allora possiamo calcolare r per tutta la ricorsiva struttura (ricordate la ricorsione è indicato esplicitamente qui con Mu):

cata :: (node r -> r) -> Mu node -> r

Rendendo questo concreto per il nostro esempio, questo appare come:

cata :: (IntNode r -> r) -> IntTree -> r

ribadire, se siamo in grado di fare un nodo con rs per i suoi figli e calcolare una r, allora possiamo calcolare una r per un intero albero.

Al fine di calcolare in realtà questo, abbiamo bisogno di essere un node Functor - che è che abbiamo bisogno di essere in grado di mappare una funzione arbitraria sui figli di un nodo

.

fmap :: (a -> b) -> node a -> node b

Questo può essere fatto semplicemente per IntNode.

fmap f (Leaf x) = Leaf x                  -- has no children, so stays the same
fmap f (Branch l r) = Branch (f l) (f r)  -- apply function to each child

Ora, , infine, , siamo in grado di dare una definizione per cata (il vincolo Functor node dice solo che ha un node fmap adatto):

cata :: (Functor node) => (node r -> r) -> Mu node -> r
cata f t = f (fmap (cata f) t)

ho usato il nome del parametro t per il valore mnemonico di "albero". Questo è un estratto, denso definizione, ma in realtà è molto semplice. Dice: ricorsivamente eseguire cata f - il calcolo che stiamo facendo sopra l'albero - su ciascuno dei figli di t (che sono essi stessi Mu nodes) per ottenere un node r, e quindi passare tale risultato f calcolare il risultato per t sé

posizionando questo nuovo all'inizio, l'algebra si sta definendo è essenzialmente un modo di definire tale funzione node r -> r. Infatti, dato un TreeAlgebra, si può facilmente ottenere la funzione duplice:

foldFunction :: TreeAlgebra a r -> (TreeNode a r -> r)
foldFunction alg (Leaf a) = leaf alg a
foldFunction alg (Branch l r) = branch alg l r

Così l'catamorphism albero può essere definito in termini di nostro generico come segue:

type Tree a = Mu (TreeNode a)

treeCata :: TreeAlgebra a r -> (Tree a -> r)
treeCata alg = cata (foldFunction alg)

Sono fuori dal tempo. So che sono davvero astratto veramente veloce, ma spero che almeno ti ha dato un nuovo punto di vista per aiutare il vostro apprendimento. Buona fortuna!

Answer 2

Credo che stavate chiedevi una domanda circa le {} s '. C'è una precedente interrogazione con una buona discussione di {} s '. Questi sono chiamati Haskell record di sintassi . L'altra domanda è: perché costruire l'algebra. Questo è un tipico paradigma funzione in cui si generalizza i dati come funzioni.

L'esempio più famoso è la costruzione della Chiesa dei Naturals , dove f = + 1 e z = 0 , 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z)), ecc ...

Quello che state vedendo è essenzialmente la stessa idea viene applicata ad un albero. Lavorare l'esempio della chiesa e l'albero si clicca.