Die Funktionsfamilie Fold steht in vielen Programmiersprachen bzw. Runtime-Umgebungen direkt zur Verfügung. In anderen modernen Sprachen ist es oft einfach, diese nachzurüsten. Im Folgenden sollen die unterschiedlichen Mitglieder der Familie vorgestellt und einige allgemeine sowie spezielle Anwendungsfälle demonstriert werden. Fold und seine Verwandten tragen regelmäßig abweichende Namen. Beliebt ist etwa „Reduce“, in LINQ hat Microsoft eine der Funktionen (das „left fold“) in Form der Funktion Aggregate ins .NET Framework aufgenommen.
Wenn Sie sich mit SQL auskennen, ist Ihnen jetzt vielleicht schon klar, was Fold grundsätzlich tut: es aggregiert Werte aus einer Datenstruktur, gewöhnlich einer Liste, und erzeugt daraus einen Resultatswert. In Listing 1 finden Sie eine Implementation der Funktion FoldL, also von „linkem“ Fold. Diese arbeitet mit IEnumerable
public static R FoldL(Func accumulator, R startVal, IEnumerable list) { R result = startVal; foreach (T sourceVal in list) result = accumulator(result, sourceVal); return result; }
Dies ist ein einfaches Anwendungsbeispiel für FoldL, die Summierung einiger Werte:
var result = FoldL((r, x) => r + x, 0, Enumerable.Range(1, 5));
Als Quelle wird hier eine Sequenz von ganzen Zahlen genutzt, die mithilfe der Funktion Range generiert werden kann (diese Funktion bzw. die Klasse Enumerable gehört zu LINQ). Der Startwert für die Berechnung einer Summe ist null. Der Akkumulator ist als Lambda-Ausdruck angegeben, mit zwei Parametern: r („Resultat“) ist der berechnete Wert der vorherigen Iteration, x ist der nächste Wert in der Sequenz. Das Resultat ist die Summe dieser beiden Werte. Der Akkumulator wird somit der Reihe nach mit folgenden Werten aufgerufen:
(0, 1) -> 1 (1, 2) -> 3 (3, 3) -> 6 (6, 4) -> 10 (10, 5) -> 15
Der Startwert ist wichtig, was sehr einfach ersichtlich ist, wenn die Berechnung im Akkumulator eine andere ist:
result = FoldL((r, x) => r * x, 1, Enumerable.Range(1, 5));
Dieser Akkumulator multipliziert die beiden Werte, und dementsprechend ist der Startwert diesmal mit 1 gewählt worden. Die Werte, mit denen Fold-Funktionen arbeiten, müssen nicht immer „einfache“ Typen sein. Listing 2 zeigt eine Anwendung der Hilfsklasse Tuple, mit deren Hilfe ein Aufruf an FoldL mehrere Werte gleichzeitig berechnen kann. Auch eine Liste kann Rückgabewert von FoldL sein – sehen Sie hierzu auch den Kasten „Map und Filter“.
public class Tuple{ private T1 val1; public T1 Val1 { get { return val1; } } private T2 val2; public T2 Val2 { get { return val2; } } public Tuple(T1 val1, T2 val2) { this.val1 = val1; this.val2 = val2; } } ... var averageResult = FoldL( (r, x) => new Tuple (r.Val1 + 1, r.Val2 + x), new Tuple (0, 0), Enumerable.Range(1, 10)); Console.WriteLine("{0} values with an average of {1}", averageResult.Val1, (double) averageResult.Val2 / averageResult.Val1);
Zusammen mit Fold sind Map und Filter Grundbausteine vieler Algorithmen. Auch diese beiden Funktionen sind unter den Namen Select und Where Bestandteil von LINQ. Map sieht so aus:
public static IEnumerableMap (Converter function, IEnumerable list) { foreach (T sourceVal in list) yield return function(sourceVal); }
Map wendet die übergebene Funktion auf jedes Element einer Liste an, die ebenfalls übergeben wird, und erzeugt als Resultat eine neue Liste, die aus den Rückgabewerten der einzelnen Funktionsaufrufe besteht. Filter arbeitet ähnlich, aber sein Resultat enthält nur diejenigen Werte, für die die Funktion ein positives Resultat liefert:
public static IEnumerableFilter (Predicate predicate, IEnumerable list) { foreach (T val in list) if (predicate(val)) yield return val; }
Fold ist von diesen drei Funktionen die weitaus mächtigste, und es ist sogar möglich, Map und Filter auf der Basis von Fold zu implementieren. Listing 3 zeigt solche Varianten von Map und Filter, der Einfachheit halber unter Verwendung der weiteren Hilfsklasse List
public static IEnumerableFoldMap (Converter converter, IEnumerable source) { return Functional.FoldL( (r, v) => r.Append(new FCSColl::List (converter(v))), FCSColl::List .Empty, source); } public static IEnumerable FoldFilter (Predicate predicate, IEnumerable source) { return Functional.FoldL( (r, v) => r.Append(predicate(v) ? new FCSColl::List (v) : FCSColl::List .Empty), FCSColl::List .Empty, source); }
Außer FoldL gehören zur Funktionsfamilie Fold einige Funktionen, die sich in einer sehr wichtigen Weise von FoldL unterscheiden: der Reihenfolge der Verarbeitung der Werte. Offensichtlich sind bei einer Liste zwei Sequenzen, nämlich die vom Anfang und die vom Ende der Liste. Das Gegenstück zu FoldL ist demnach FoldR, also rechtes anstelle von linkem Falten.
Hinterlasse einen Kommentar
Hinterlasse den ersten Kommentar!