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 IEnumerableals Quelle der Daten, kann also somit auf jeden Listentyp in .NET angewendet werden. Die Funktion iteriert über die Elemente der Liste und ruft für jedes Element einmal die Funktion accumulator auf, die an FoldL als Parameter übergeben wird. Diese Funktion führt die eigentliche Akkumulation der Werte durch, was große Flexibilität zur Folge hat – indem die Implementation des Akkumulators variiert wird, kann FoldL den unterschiedlichsten Anwendungsfällen gerecht werden. Schließlich ist FoldL generisch, so dass mit beliebigen Typen gearbeitet werden kann. Der zweite Parameter von FoldL ist der so genannte Startwert. Während der Iteration werden dem Akkumulator jeweils zwei Parameter übergeben: das Resultat der vorherigen Iteration und der Wert der Liste, der aktuell verarbeitet wird. Beim ersten Element der Liste gibt es aber noch kein Resultat von einer vorherigen Iteration, hier kommt stattdessen der Startwert zum Einsatz. Je nach Einsatzzweck von FoldL muss der Startwert angepasst werden, damit dieser Wert im Kontext der verwendeten Akkumulation sinnvoll ist.

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 IEnumerable Map(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 IEnumerable Filter(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. Dabei handelt es sich nicht um die normale Klasse System.Collections.Generic.List. Die komplette Darstellung dieser Klasse würde den Rahmen dieses Artikels sprengen, jedoch ist zum Verständnis des Codes nur wichtig zu wissen, dass die Funktion Append eine andere Liste an die aktuelle anhängt und die Property Empty eine leere Instanz einer Liste eines bestimmten Typs zurückliefert.

public static IEnumerable FoldMap(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.