Wie Sie vielleicht wissen, gibt es in OCaml Funktionen wie fold_left, fold_right, filter etc.
Auf meinem Kurs in funktionaler Programmierung wurde Funktion namens fold_tree eingeführt, die etwas wie fold_left / right, nicht auf Listen, sondern auf (binären) Bäumen ist. Es sieht so aus:
%Vor%Wo Baum definiert ist als:
%Vor%OK, hier ist meine Frage: Wie funktioniert die Funktion falt_tree? Können Sie mir einige Beispiele geben und in menschlicher Sprache erklären?
Hier ist ein Stilvorschlag, setzen Sie die Balken am Anfang der Zeile. Es macht deutlicher, wo ein Fall beginnt. Aus Konsistenzgründen ist der erste Balken optional, wird aber empfohlen.
%Vor%Wie es funktioniert, betrachten Sie den folgenden Baum:
%Vor% Mit dem Typ int tree .
Visuell sieht t folgendermaßen aus:
Und wenn wir fold_tree aufrufen, brauchen wir eine Funktion, um die Werte zu kombinieren. Basierend auf der Verwendung im Fall Node benötigt f 3 Argumente, alle vom selben Baumtyp und gibt dasselbe zurück. Wir machen das:
Es würde helfen zu verstehen, was in jedem Fall passiert. Für Leaf wird a zurückgegeben. Für jede Node kombiniert sie den gespeicherten Wert und das Ergebnis der Faltung 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 .
Nehmen wir einen Beispielbaum.
%Vor%Die allgemeine Definition einer falten Operation besteht darin, dass Sie Konstruktoren durch Funktionen überall in ersetzen der Baum.
%Vor% node ist eine Funktion, die ein etwas aus einem linken etwas , einem Element und einem rechten Etwas , genau wie% co_de, konstruiert % ist ein Konstruktor, der einen Baum aus einem linken Teilbaum, einem Knoteninhalt und einem rechten Teilbaum konstruiert. Node ist eine Konstante, die dem Konstantenkonstruktor leaf entspricht.
Beachten Sie, dass die Typen der Funktionen mit denen der Typdefinition übereinstimmen, außer dass die Typdefinition, wenn die Typdefinition die Erstellung eines Leaf beschreibt, die Erstellung eines beliebigen 'a tree beschreibt.
Operationen, die der allgemeinen Faltung sehr ähnlich sind, werden immer noch Falte genannt. In Listen beispielsweise ist 'b die allgemeine Falte gemäß der obigen Definition; List.fold_right ist eine Variation, die die Funktion anders herum anwendet ( List.fold_left ist gleichbedeutend mit reverse + fold_left + reverse, obwohl es klarer und effizienter ist).
Ihre eigene fold_right ist eine einfache Variante dieser allgemeinen Faltung, bei der die Knotenfunktion ihre Argumente in einer anderen Reihenfolge als der Konstruktor verwendet:
Hier ist eine Möglichkeit, über fold_right auf Listen nachzudenken: Eine Liste ist zum Beispiel
und Sie interpretieren die Liste mit einer neuen binären Operation anstelle von :: (und einer neuen Konstante anstelle von []) neu.
%Vor% Wenn Sie Ihrer Liste absolut nichts hinzufügen wollten, könnten Sie die Funktion cons als Funktion und die leere Liste als neutrales Element übergeben. In gewisser Hinsicht ist fold_right sehr allgemein gehalten: Sie können sogar gar keine Informationen 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 Morphismus ).
Sie können die Elemente des Baums auch mit der Funktion (fun x l r -> x + l + r) zum Beispiel summieren.
Es scheint, dass f eine Reduktionsfunktion mit drei Parametern ist, a ist das neutrale Element unserer Reduktion und t ist die Wurzel, also:
binär wie (ich erinnere mich nicht sehr gut an die Syntax von Variant-Typen, bitte seien Sie hier).
%Vor%Wenn Sie alle Knoten summieren möchten, wird die Funktion wie folgt aufgerufen:
%Vor% und wir erhalten t als Knoten, also haben wir:
Wenn wir es ein wenig erweitern, erhalten wir:
%Vor%und noch einmal, wir passen die Blätter zusammen:
%Vor%um endlich zu bekommen:
%Vor%Ich hoffe, es hilft.
Tags und Links functional-programming ocaml higher-order-functions