fold_tree in OCaml

Question

Wie Sie vielleicht wissen, gibt es Funktionen höherer Ordnung in OCaml, wie fold_left, fold_right, Filter etc.

Auf meinen Kurs in die funktionale Programmierung hatte Funktion mit dem Namen fold_tree eingeführt, die so etwas wie fold_left ist/rechts, nicht auf Listen, sondern auf (binären) Bäumen. Es sieht wie folgt aus:

let rec fold_tree f a t = 
    match t with 
    Leaf -> a | 
    Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

Wo Baum wie folgt definiert ist:

type 'a tree = 
    Node of 'a tree * 'a * 'a tree | 
    Leaf;; 

OK, hier ist meine Frage: Wie funktioniert die fold_tree Funktion Arbeit? Kannst du mir ein paar Beispiele geben und in menschlicher Sprache erklären?

Answer 1

Hier ist ein Stilvorschlag, legen Sie die Balken am Anfang der Zeile. Es macht deutlicher, wo ein Fall beginnt. Aus Konsistenzgründen ist der erste Balken optional, wird jedoch empfohlen.

type 'a tree = 
    | Node of 'a tree * 'a * 'a tree 
    | Leaf;; 

let rec fold_tree f a t = 
    match t with 
     | Leaf -> a 
     | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

---

Was, wie es funktioniert, sollten Sie die folgenden Baum:

let t = Node(Leaf, 5, Node(Leaf, 2, Leaf));; 

Mit dem Typ int tree.

Optisch sieht t wie folgt aus:

 
    5 
/\ 
() 2 
    /\ 
    ()() 

Und ruft fold_tree wir eine Funktion bräuchten die Werte zu kombinieren. Basierend auf der Verwendung in dem Node Fall, f dauert 3 Argumente, alle den gleichen Typ des Baumes und gibt das gleiche zurück. Wir machen das:

let f x l r = x + l + r;; (* add all together *) 
fold_tree f 1 t;; 

Es würde helfen zu verstehen, was in jedem Fall passiert.Für jede Leaf wird ein zurückgegeben. Für jede Node, kombiniert es den gespeicherten Wert und das Ergebnis des Faltens der linken und rechten Teilbäume. In diesem Fall fügen wir nur die Zahlen hinzu, bei denen jedes Blatt als eins zählt. Das Ergebnis der Faltung dieses Baumes ist 10.

Answer 2

Es scheint, dass f eine Reduktion Funktion drei Parameter ist, ist a das neutrale Element unserer Reduktion und t ist die Wurzel, so:

eine binäre wie (ich die Syntax sehr gut weiß nicht mehr gegeben Arten Variante condescendent hier)

let r = Node(Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf)),1,Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf))) 

wenn Sie wie alle Knoten summieren möchten werden, wird die Funktion so bitte aufgerufen werden:

let add x y z = x + y + z 
fold_tree add 0 r 

und wir werden t als Knoten angepasst bekommen, so haben wir:

(add 1 (fold_tree add 0 Node(Node(Leaf,3,Leaf),2,Node(Leaf,4,Leaf))) (fold_tree add 0 Node(Node(Leaf,6,Leaf),5,Node(Leaf,7,Leaf)))) 

wenn wir es ein wenig mehr zu erweitern, erhalten wir:

(add 1 (add 2 (fold_tree add 0 Node(Leaf,3,Leaf)) (fold_tree add 0 Node(Leaf,4,Leaf))) (add 5 (fold_tree add 0 Node(Leaf,6,Leaf)) (fold_tree add 0 Node(Leaf,7,Leaf)))) 

und noch einmal, wir passen die Blätter:

(add 1 (add 2 (add 3 0 0) (add 4 0 0)) (add 5 (add 6 0 0) (add 7 0 0)) 
(add 1 (add 2 3 4) (add 5 6 7)) 
(add 1 9 18) 

endlich zu bekommen:

28 

Hoffe es hilft.

Answer 3

Hier ist ein Weg, um über fold_right auf Listen zu denken: eine Liste zum Beispiel ist

(1 :: (2 :: (3 :: []))) 

und Sie neu interpretieren die Liste mit einem neuen binären Operation anstelle von :: (und eine neue Konstante statt von []).

fold_right (+) l 0 = (1 + (2 + (3 + 0))) 

Wenn Sie absolut nichts zu Ihrer Liste tun möchten, können Sie die Funktion cons wie die Funktion und die leere Liste als neutrales Element übergeben. In gewisser Hinsicht ist fold_right sehr allgemein gehalten: Es erlaubt Ihnen sogar, keine Informationen zu verlieren.

Die fold_tree in Ihrer Frage ist die gleiche Idee für den Datentyp von Bäumen. Wenn Sie Ihren Baum neu interpretieren möchten, übergeben Sie ihm eine neue Funktion für Knoten, die anstelle des Konstruktors Node angewendet werden. Wenn Sie einen identischen Baum erhalten möchten, können Sie ihn mit Leaf als neutral und (fun x l r -> Node (l, x, r)) als Funktion anwenden. Ähnlich wie fold_left für Listen ist diese Beispielanwendung nicht sehr interessant, aber es bedeutet, dass fold_left eine sehr allgemeine Transformation ist (der Fachausdruck ist morphism).

Sie können zum Beispiel auch die Elemente des Baums mit der Funktion (fun x l r -> x + l + r) summieren.

Answer 4

Nehmen wir einen Beispielbaum.

let t = Node (Node (Leaf, 10, Leaf), 1, Node (Node (Leaf, 20, Leaf), 11, Leaf)) 

Die allgemeine Definition eines fold Betrieb ist, dass Sie Konstrukteure von Funktionen, überall in der Struktur ersetzen.

general_fold_tree node leaf t = 
    node (node leaf 10 leaf) 1 (node (node leaf 20 leaf) 11 leaf) 

node ist eine Funktion, die eine etwas von einer linken etwas, einem Element und einem rechten etwas, wie Node ist ein Konstruktor-Konstrukte, die einen Baum von einer linken Unterbaum konstruiert, ein Knoten Inhalt und ein rechter Teilbaum. leaf ist eine Konstante, die Leaf Konstanten Konstruktor entspricht.

let rec general_fold_tree (node : 'b -> 'a -> 'b -> 'b) (leaf : 'a) (t : 'a tree) : 'b = 
    let recurse t = general_fold_tree node leaf t in 
    match t with 
    | Node (l, x, r) -> node (recurse l) x (recurse r) 
    | Leaf -> leaf 

Beachten Sie, dass die Typen der Funktionen denen des Typ-Definition entsprechen, mit der Ausnahme, dass, wenn die Typdefinition den Bau einer 'a tree beschreibt, die Falzfunktion das Gebäude eines 'b beschreibt.

Operationen, die wie die allgemeine Faltung aussehen, werden immer noch Falte genannt. Zum Beispiel ist in den Listen List.fold_right die allgemeine Faltung gemäß der obigen Definition; List.fold_left ist eine Variante, die die Funktion anders herum anwendet (fold_left entspricht umgekehrt + fold_right + umgekehrt, obwohl es klarer und effizienter ist).

Ihre eigene fold_tree ist eine einfache Variante dieses allgemeinen Falte, wo die Knotenfunktion ihre Argumente in einer anderen Reihenfolge aus dem Konstruktor:

let equrts_fold_tree f a t = 
    let node l x r = f x l r in 
    general_fold_tree node a t 

Answer 5

Sie lesen vielleicht genießen

http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/

http://lorgonblog.wordpress.com/2008/04/09/catamorphisms-part-three/

die in F # sind, aber F # ist sehr ähnlich nach OCaml.