Katamorphismus und Baumdurchquerung in Haskell

Question

Ich bin ungeduldig und freue mich darauf, den Katamorphismus zu verstehen im Zusammenhang mit dieser SO-Frage :)

Ich habe nur den Anfang des Real World Haskell-Tutorials geübt.Also, vielleicht werde ich jetzt viel zu viel verlangen, wenn es der Fall wäre, sagen Sie mir einfach die Konzepte, die ich lernen sollte.

Nachfolgend zitiere ich die Wikipedia-Codebeispiel für Katamorphismus.

Ich würde gerne Ihre Meinung zu FoldTree unten erfahren, einer Möglichkeit, einen Baum zu durchqueren, im Vergleich zu dieser anderen SO-Frage und Antwort, die sich ebenfalls mit dem Durchqueren eines Baums befasst n-äre Baumdurchquerung.(Unabhängig davon, ob es binär ist oder nicht, denke ich, dass der folgende Katamorphismus so geschrieben werden kann, dass er einen n-ären Baum verwaltet.)

Ich gebe in einem Kommentar ab, was ich verstehe, und freue mich, wenn Sie mich korrigieren und einige Dinge klarstellen könnten.

{-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)

Zu diesem Zeitpunkt habe ich viele Schwierigkeiten, ich scheine zu vermuten, dass das Morphismusblatt auf jedes Blatt angewendet wird, aber um diesen Code für Real zu verwenden, muss FoldTree eine definierte Treealgebra, eine Treealgebra, mit einem definierten Morphismusblatt gefüttert werden um etwas zu tun?
aber in diesem Fall würde ich im FoldTree-Code {f = leaf} erwarten und nicht das Gegenteil

Jede Klarstellung Ihrerseits wäre uns sehr willkommen.

Answer 1

Ich bin mir nicht ganz sicher, was Sie fragen.Aber ja, du fütterst einen TreeAlgebra Zu foldTree entsprechend der Berechnung, die Sie für den Baum durchführen möchten.Um beispielsweise alle Elemente in einem Baum zu summieren Ints Sie würden diese Algebra verwenden:

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

Das heißt, um die Summe eines Blattes zu erhalten, wenden Sie an id (nichts tun) auf den Wert im Blatt.Um die Summe einer Verzweigung zu erhalten, addieren Sie die Summen von jedem der Kinder.

Die Tatsache, dass wir sagen können (+) für branch statt, sagen wir, \x y -> sumTree x + sumTree y ist die wesentliche Eigenschaft des Katamorphismus.Es heißt, dass man eine Funktion berechnen soll f Bei einer rekursiven Datenstruktur reicht es aus, die Werte von zu haben f für seine unmittelbaren Kinder.

Haskell ist insofern eine ziemlich einzigartige Sprache, als wir die Idee des Katamorphismus abstrakt formalisieren können.Erstellen wir einen Datentyp für einen einzelnen Knoten in Ihrem Baum, parametrisiert über seine untergeordneten Knoten:

data TreeNode a child
    = Leaf a
    | Branch child child

Sehen Sie, was wir dort gemacht haben?Wir haben einfach die rekursiven Kinder durch einen Typ unserer Wahl ersetzt.Dies dient dazu, dass wir beim Falten die Summen der Teilbäume dort ablegen können.

Nun zum wirklich Magischen.Ich werde dies in Pseudohaskell schreiben – es ist möglich, es in echtem Haskell zu schreiben, aber wir müssen einige Anmerkungen hinzufügen, um der Typprüfung zu helfen, was etwas verwirrend sein kann.Wir nehmen den „Fixpunkt“ eines parametrisierten Datentyps – das heißt, wir konstruieren einen Datentyp T so dass T = TreeNode a T.Sie nennen diesen Operator Mu.

type Mu f = f (Mu f)

Schauen Sie hier genau hin.Das Argument zu Mu ist kein Typ, wie Int oder Foo -> Bar.Es ist ein Typ Konstrukteur wie Maybe oder TreeNode Int -- das Argument zu Mu selbst braucht ein Argument.(Die Möglichkeit, über Typkonstruktoren zu abstrahieren, ist eines der Dinge, die das Typsystem von Haskell in seiner Ausdruckskraft wirklich hervorheben.)

Also der Typ Mu f wird als Nehmen definiert f und seinen Typparameter mit ausfüllen Mu f selbst.Ich werde ein Synonym definieren, um das Rauschen etwas zu reduzieren:

type IntNode = TreeNode Int

Erweitern Mu IntNode, wir bekommen:

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

Siehst du wie Mu IntNode entspricht Ihrem Tree Int?Wir haben die rekursive Struktur einfach auseinandergerissen und dann verwendet Mu um es wieder zusammenzusetzen.Das gibt uns den Vorteil, dass wir über alles reden können Mu Typen auf einmal.Dies gibt uns, was wir brauchen, um einen Katamorphismus zu definieren.

Definieren wir:

type IntTree = Mu IntNode

Ich sagte, die wesentliche Eigenschaft des Katamorphismus besteht darin, eine Funktion zu berechnen f, es reicht aus, die Werte von zu haben f für seine unmittelbaren Kinder.Nennen wir den Typ der Sache, die wir berechnen möchten r, und die Datenstruktur node (IntNode wäre eine mögliche Instanziierung davon).Also zum Berechnen r Auf einem bestimmten Knoten müssen wir den Knoten mit seinen untergeordneten Knoten durch ihre ersetzen rS.Diese Berechnung hat Typ node r -> r.Ein Katamorphismus besagt also, dass wir rechnen können, wenn wir eine dieser Berechnungen haben r für das ganze rekursiv Struktur (denken Sie daran, dass Rekursion hier explizit mit bezeichnet wird Mu):

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

Konkret für unser Beispiel sieht das so aus:

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

Um es noch einmal zu sagen: Wenn wir einen Knoten mitnehmen können rs für seine Kinder und berechnen Sie an r, dann können wir an berechnen r für einen ganzen Baum.

Um dies tatsächlich zu berechnen, benötigen wir node ein ... zu sein Functor – das heißt, wir müssen in der Lage sein, eine beliebige Funktion über die Kinder eines Knotens abzubilden.

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

Dies kann unkompliziert durchgeführt werden 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

Jetzt, Endlich, wir können eine Definition dafür geben cata (Die Functor node Einschränkung sagt das einfach node hat ein passendes fmap):

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

Ich habe den Parameternamen verwendet t für den mnemonischen Wert von „tree“.Dies ist eine abstrakte, dichte Definition, aber eigentlich ist sie sehr einfach.Es sagt:rekursiv ausführen cata f – die Berechnung, die wir über den Baum durchführen – für jeden von ihnen t's Kinder (die sie selbst sind Mu nodes) um ein zu bekommen node r, und übergeben Sie das Ergebnis dann an f Berechnen Sie das Ergebnis für t selbst.

Um dies auf den Anfang zurückzubringen: Die Algebra, die Sie definieren, ist im Wesentlichen eine Möglichkeit, dies zu definieren node r -> r Funktion.In der Tat, gegeben a TreeAlgebra, können wir leicht die Faltfunktion erhalten:

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

Somit kann der Baumkatamorphismus in Bezug auf unseren generischen Katamorphismus wie folgt definiert werden:

type Tree a = Mu (TreeNode a)

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

Ich habe keine Zeit mehr.Ich weiß, das wurde sehr schnell sehr abstrakt, aber ich hoffe, es hat Ihnen zumindest einen neuen Blickwinkel vermittelt, der Ihnen beim Lernen hilft.Viel Glück!

Answer 2

Ich glaube, Sie wurden eine Frage zu dem {} s zu fragen. Es ist eine frühere Frage mit einer guten Diskussion {} s. Diese werden Haskell Rekord Syntax genannt. Die andere Frage ist, warum die Algebra konstruieren. Dies ist eine typische Funktion Paradigma, wo man Daten als Funktionen verallgemeinern.

Das bekannteste Beispiel ist Kirche Bau der Naturals , wo f = + 1 und z = 0 . 0 = z, 1 = f z, 2 = f (f z), 3 = f (f (f z)), etc ...

Was Sie sehen, ist im Wesentlichen die gleiche Idee zu einem Baum angewandt wird. Die Arbeit der Kirche Beispiel und der Baum wird klicken.