WikiDer > Falten

Im funktionale Programmiersprachen ist ein falten (oder reduzieren) ein Funktion höherer Ordnung mit dem a rekursivDatenstruktur analysiert werden kann. In vielen Fällen a aufführen in einer bestimmten Reihenfolge und nach und nach wird ein bestimmter Wert berechnet. Ein Fold verwendet zwei Dinge: eine Funktion, die Elemente der Datenstruktur und die Datenstruktur selbst kombiniert. Ein Beispiel:

falten ( ) [1,2,3,4,5]

was zu 1 2 3 4 5 = 15 führt. In diesem Beispiel ist ' ' a assoziative Operation macht es irrelevant, wie die Klammern platziert werden. Als Annäherung an die Funktionsweise von fold könnte man die Kommas in der Liste durch die angegebene Funktion ersetzen.

foldr und foldl

Normalerweise ist die Funktion nicht assoziativ, daher spielt die Reihenfolge, in der die Berechnung durchgeführt wird, eine Rolle. In Listen gibt es zwei Möglichkeiten, dies zu tun: Man beginnt rechts mit dem Setzen der Klammern und gibt ein rekursiv die Berechnung aus (a rechte Falte) oder man beginnt links (a linke Falte). Oft wird auch ein Anfangswert verwendet, um die Berechnung durchzuführen. Je nachdem, was man berechnen möchte, kann dies a neutrales Element sind auch ein anderer Wert. Ein Beispiel für a rechte Falte im Haskell (dies geschieht mit der Funktion Ordner):

Ordner ( ) 0 [1,2,3,4]

Diese Berechnung ist gleich (1 (2 (3 (4 0))))) = 10. Ein Beispiel für a linke Falte:

falten (-) 100 [1,2,3,4]

Dies ist gleich (((((100 - 1) - 2) - 3) - 4) = 90.

Die Funktionen falten und Ordner kann in Haskell wie folgt definiert werden (in Haskell . is [] eine leere Liste und (x:xs) eine Liste von X als erstes Element und xs der Rest der Liste):

foldr fz [] = z -- wenn die Liste leer ist, ist der zurückgegebene Wert der Anfangswert foldr fz (x:xs) = fx (foldr fz xs) -- andernfalls wenden Sie f auf das erste Element und das Ergebnis von foldr . an zum Rest

foldl fz [] = z -- wenn die Liste leer ist, ist der zurückgegebene Wert der Anfangswert foldl fz (x:xs) = foldl f (fzx) xs -- andernfalls berechnen Sie einen neuen Anfangswert, indem Sie f auf die Initiale anwenden value und -- das erste Element und wende foldl mit diesem Wert auf den Rest der Liste an

Ein wichtiger Punkt ist das Ordner Biene faule Bewertung oder normale Auftragsauswertung sofort f gilt für den rekursiven Aufruf von Foldr an den Rest der Liste. wenn f kann einen Teil des Ergebnisses erzeugen, ohne den rekursiven Aufruf zu verwenden, und wenn der Rest des Ergebnisses nie benötigt wird, wird der rekursive Aufruf nicht ausgeführt. Auf diese Weise kann Foldr mit unendlichen Listen umgehen. falten ruft sich jedoch mit new auf Parameter bis das Ende der Liste erreicht ist. Dieses Schwanzrekursion kann effizient sein zusammengestellt ist wie eine Schleife, kann aber keine unendlichen Listen verarbeiten (dies führt zu a Endlosschleife).

Ein weiterer technischer Punkt ist, dass der neue Anfangswert bei falten in solchen Programmiersprachen wird erst berechnet, wenn der rekursive Aufruf ausgeführt wird. Dies kann dazu führen Stapelüberläufe wenn das Ende der Liste erreicht ist und es zu einem Riesen wird Ausdruck rechnen muss. Aus diesem Grund haben solche Programmiersprachen auch eine streng Version von falten die zuerst den neuen Anfangswert berechnet, bevor der rekursive Aufruf erfolgen kann. In Haskell ist das falten (mit Apostroph, gefunden im Daten.ListeBibliothek). In Kombination mit der Geschwindigkeit der Tail-Rekursion sind solche Falten sehr effizient, wenn eine faule Berechnungsmethode unmöglich oder unerwünscht ist.

Im planen können Ordner und falten geschrieben werden als:

(define (foldr f z xs) (if (null? xs) z (f (car xs) (foldr f z (cdr xs)))))

(define (foldl f z xs) (if (null? xs) z (foldl f (f z (car xs)) (cdr xs)))))

Das C Standardvorlagenbibliothek Bibliothek implementiert fold als "akkumulieren" (im Header).

foldl1 und foldr1

In bestimmten Situationen will man falten oder Ordner aber es ist kein passender Anfangswert zu denken, wenn man beispielsweise den Maximalwert in der Liste mit einer Funktion berechnet, die den größeren der beiden Parameter zurückgibt. Es gibt Varianten von falten und Ordner die keinen Anfangswert verwenden, sondern das erste oder letzte Element der Liste als Startwert verwenden. In Haskell und in einigen anderen Sprachen heißen diese foldl1 und Ordner1 wobei die 1 darauf hinweist, dass das erste Element (von links oder von rechts) als Startwert verwendet wird und dass die Listen, auf die sie angewendet werden, mindestens ein Element enthalten müssen.

Die Funktion maximal was das größte Element einer Liste zurückgibt, löst einen Fehler aus, wenn es auf eine leere Liste wie folgt angewendet wird:

maximal = foldl1 max

Standartfunktionen

Viele Standardfunktionen in funktionalen Programmiersprachen lassen sich über eine Faltfunktion schreiben:

und = Ordner (&&) Wahr (Beiträge logische Konjunktion zwischen den Elementen einer Liste boolesche Werte)

oder = Ordner (||) Falsch (Beiträge logische Disjunktion zwischen den Elementen in einer Liste von booleschen Werten)

Summe = Ordner ( ) 0 (summieren, fügt Elemente einer Liste zusammen)

Produkt = Ordner (*) 1 (multiplizieren, multipliziert die Elemente einer Liste)

concat = Ordner ( ) [] (Verkettung, nämlich: konkat [[1], [2], [3]] = [1,2,3])

( ) xs ys = Ordner (:) ys xs (Verkettung, nämlich: [1,2] [3,4] = [1,2,3,4])

maximal = foldl1 max (liefert das größte Element in der Liste)

Minimum = foldl1 min (gibt das kleinste Element in der Liste zurück)

Ordner f = Ordner ((:).f) [] (die Funktion Mappe; siehe auch unten)

reverse = foldr(ab -> b[a]) [] (gibt die Liste der Elemente in umgekehrter Reihenfolge)

Ein anderer Versuch

Faltfunktionen können als eine Möglichkeit angesehen werden, die strukturellen Komponenten einer Datenstruktur durch Funktionen und Werte zu ersetzen. In vielen Sprachen eine Liste oder eine leere Liste (auf Englisch Null genannt) oder eine Liste, die durch Hinzufügen eines Elements zu einer vorhandenen Liste erstellt wird. In Haskell wird eine Liste mit dem (:) Funktion, diese wird auch genannt Nachteile oder "Konstruktor" genannt, weil es eine Liste erstelltNachteileist wahr. Im planen und lispeln heißt das OperatorNachteile. Ein Beispiel dafür ist die Liste [1,2,3,4,5], das ist eigentlich ein einfachere Notation vor dem 1:2:3:4:5:[]. Eine Liste wird erstellt, indem zuerst das Element 5 zur leeren Liste hinzugefügt wird ([5]), dann wird 4 zu dieser Liste hinzugefügt ([4,5]), und so weiter.

Man kann rechte Falte Erwägen Sie, die leere Liste durch einen bestimmten Wert zu ersetzen (den Anfangswert, der an die Funktion fold übergeben wird) und ein beliebiges en (:) durch die angegebene Funktion:

Wie arbeiten falten ist etwas weniger natürlich, hat aber eine regelmäßige Struktur:

Wie arbeiten foldl1 und Ordner1 kann man sich auch so vorstellen:

Abgesehen davon, dass diese Bilder Recht und links Betrieb von jeweils Ordner und falten Display zeigt auch, dass Mappe (:) [] ein Identitätsfunktion für eine Liste ist: Ausführen Ordner (:) [] l gibt für jede Liste dieselbe Liste zurück l.

Es faltenDiagramm schlägt eine Möglichkeit vor, die Elemente einer Liste in umgekehrter Reihenfolge zurückzugeben: foldl (flip(:)) []. Die Funktion umdrehen dreht die Reihenfolge der Parameter zu. Dies ist notwendig, da das der Liste hinzuzufügende Element nun der richtige Parameter des the (:) Funktion.

Auf diese Weise kann man auch sehen, dass die Funktion höherer Ordnung Mappe kann geschrieben werden mit Ordner:

Ordner f = Ordner ((:).f) []

bei welchem (.) (ein Punkt) der Operator für Funktionszusammenstellung schlägt vor.

Dieser Ansatz ermöglicht es, Faltfunktionen für algebraische Datentypen, wie Bäume. Man schreibt eine Funktion, die rekursiv die Konstruktoren der Datenstruktur durch Funktionen und die konstanten Werte durch vorgegebene Werte ersetzt. Dieses Prinzip wird Katamorphismus erwähnt.