Die Kunst des Faltens (Teil 2)
Kommentare

Zunächst zur Theorie: FoldL und FoldR haben im Allgemeinen drei wichtige Unterschiede, von denen allerdings in C# nur einer relevant ist. Dieser wichtige Grund für die Entscheidung für eine dieser beiden

Zunächst zur Theorie: FoldL und FoldR haben im Allgemeinen drei wichtige Unterschiede, von denen allerdings in C# nur einer relevant ist. Dieser wichtige Grund für die Entscheidung für eine dieser beiden Funktionen ist die so genannte Assoziativität der Operation, die in der Akkumulation angewendet wird. Eine assoziative Funktion ist etwa Plus, weil diese beiden Ausdrücke das gleiche Ergebnis haben:

((1 + 2) + 3) + 4 1 + (2 + (3 + 4))

Tatsächlich könnten bei diesem Ausdruck die Klammern auch ganz anders oder gar nicht gesetzt werden – Plus ist eine assoziative Funktion. Ganz anders bei Minus:

((1 – 2) – 3) – 4 -> -8 1 – (2 – (3 – 4)) -> -2

In Listing 4 finden Sie eine rekursive Implementation von FoldL, und eine Variante davon, die mit einigen Debug-Ausgaben versehen wurde. Es wird wiederum die Klasse List verwendet, die schon im Kasten „Map und Filter“ angesprochen wurde. Die Rekursion macht die Implementation extrem elegant und einfach – in .NET ist in der Praxis sicher eine Implementation, basierend auf Iteratoren, vorzuziehen, aber zur Demonstration des Verhaltens von Fold eignet sich die einfachste Umsetzung am besten.

In dem Beispiel wird eine einfache Summe berechnet, dabei werden allerdings alle Schritte auf der Konsole ausgegeben. Hier ist das Ergebnis:

flr(acc, 0, [1, 2, 3])
accD(0, 1) ... returning 1
flr(acc, 1, [2, 3])
accD(1, 2) ... returning 3
flr(acc, 3, [3])
accD(3, 3) ... returning 6
flr(acc, 6, []) ... returning 6
6  

Wie Sie sehen, wird der Akkumulator auf die Werte der Liste von links nach rechts angewendet. Bei jedem Aufruf wird das vorherige Ergebnis wiederverwendet, während die Liste selbst immer kürzer wird. In der rekursiven Implementation ist der Unterschied zwischen FoldL und FoldR sehr gering. Listing 5 zeigt das gleiche Beispiel mit FoldR. Dessen Ausgabe ist jedoch diese:

Die Reihenfolge, in der die Akkumulation durchgeführt wird, ist bei FoldR umgekehrt. Was ebenfalls anders erscheint, ist die Verwendung des Startwertes – dieser wird nach wie vor beim ersten Aufruf des Akkumulators übergeben, aber natürlich ist das bei FoldR der letzte Wert der Liste, nicht der erste wie bei FoldL.

Es gibt in anderen Programmiersprachen zwei weitere Gründe, sich für eine der beiden Varianten zu entscheiden. Diese sind in C# nicht relevant, sollen aber der Vollständigkeit halber erwähnt werden. Der erste Grund hat mit Rekursion zu tun. In vielen Programmiersprachen würde eine praktische Implementation der beiden Funktionen tatsächlich rekursiv erfolgen. In C# bietet sich Rekursion nicht an, und der einfachste Grund dafür ist, dass C# die so genannte „tail recursion“ nicht unterstützt, so dass rekursive Funktionen sehr einfach Stack Overflow Exceptions auslösen können. Tail recursion bedeutet in Kürze, dass der Compiler keine Rücksprungadressen auf dem Stack ablegt, wenn der letzte Aufruf in einer Funktion eben der rekursive Aufruf ihrer selbst ist – wie im Beispiel des rekursiven FoldLRec zu sehen ist. FoldRRec hingegen hat als letztes Statement den Aufruf des Akkumulators, so dass hier tail recursion nicht angewendet werden kann. In Sprachen, die hierfür Unterstützung haben, ist dieser Unterschied eventuell relevant.

Der zweite Grund geht ebenfalls auf ein Feature zurück, dass manche Sprachen haben: „lazy evaluation“ oder wissenschaftlicher, „nicht-strikte Auswertung“. C# verwendet weitestgehend strikte Auswertung, wobei Parameter vor ihrer Übergabe an eine Funktion ausgewertet werden. Nicht-strikte Auswertung (das bekannteste Beispiel für eine Sprache, die diesen Mechanismus verwendet, ist Haskell) hingegen bedeutet, dass Parameter erst ausgewertet werden, wenn ihre Werte tatsächlich benötigt werden, also womöglich irgendwann während der Ausführung der aufgerufenen Funktion oder auch niemals. Unter solchen nicht-strikten Umständen ist die rekursive Implementation von FoldR in der Lage, mit Listen unendlicher Länge zu arbeiten. Natürlich kann es niemals ein Ergebnis berechnen, aber dies ist trotzdem ein wichtiger Unterschied im Vergleich zu FoldL, das bei Übergabe einer unendlich langen Liste einfach eine Endlosschleife bilden würde.

public static R FoldLRec(Func acc, R start, List list) {
  if (list == List.Empty)
    return start;
  return FoldLRec(acc, acc(start, list.Head), list.Tail);
}

public static R FoldLRecD(Func acc, R start, List list) {
  Console.Write("flr(acc, {0}, {1})", start, list);
  if (list == List.Empty) {
    Console.WriteLine(" ... returning {0}", start);
    return start;
  }
  else
    Console.WriteLine( );
  return FoldLRecD(acc, acc(start, list.Head), list.Tail);
}

...

var onetothree = new List(Enumerable.Range(1, 3));
      
Func accD = (r, x) => {
  int sum = r + x;
  Console.WriteLine("accD({0}, {1}) ... returning {2}", r, x, sum);
  return sum;
};
var resultL = FoldLRecD(accD, 0, onetothree);
Console.WriteLine(resultL);  
public static R FoldRRec(Func acc, R start, List list) {
  if (list == List.Empty)
    return start;
  return acc(list.Head, FoldRRec(acc, start, list.Tail));
}

public static R FoldRRecD(Func acc, R start, List list) {
  Console.Write("frr(acc, {0}, {1})", start, list);
  if (list == List.Empty) {
    Console.WriteLine(" ... returning {0}", start);
    return start;
  }
  else
    Console.WriteLine( );
  return acc(list.Head, FoldRRecD(acc, start, list.Tail));
}

...

Func accRD = (x, r) => {
  int sum = r + x;
  Console.WriteLine("accRD({0}, {1}) ... returning {2}", r, x, sum);
  return sum;
};
var resultR = FoldRRecD(accRD, 0, onetothree);
Console.WriteLine(resultR);  
public static R FoldR(Func accumulator, R startVal, 
  IEnumerable list) {
  return FoldL((r, x) => accumulator(x, r), startVal, Reverse(list));
}

public static T FoldL1(Func accumulator, IEnumerable list) {
  return FoldL(accumulator, First(list), Skip(1, list));
}

public static T FoldR1(Func accumulator, IEnumerable list) {
  return FoldL1((r, x) => accumulator(x, r), Reverse(list));
}

public static IEnumerable Reverse(IEnumerable source) {
  List stack = List.Empty;
  foreach (T item in source)
    stack = stack.Cons(item);
  while (stack != List.Empty) {
    yield return stack.Head;
    stack = stack.Tail;
  }
}

public static T First(IEnumerable source) {
  var enumerator = source.GetEnumerator( );
  enumerator.MoveNext( );
  return enumerator.Current;
}

public static IEnumerable Skip(int count, IEnumerable source) {
  int skipped = 0;
  foreach (T item in source) {
    if (skipped < count) {
      skipped++;
      continue;
    }
    yield return item;
  }
}  

In Listing 6 finden Sie eine Implementation von FoldR, die auf IEnumerable basiert. Diese verwendet eine Hilfsfunktion Reverse, die ebenfalls in dem Listing enthalten ist. Die Originalliste wird in ihrer Reihenfolge umgekehrt und somit rückwärts bearbeitet. So kommt diese Funktion ohne die in C# problematische Rekursion aus. Listing 6 enthält weiterhin je eine Variante zu FoldL und FoldR, unter den Namen FoldL1 und FoldR1. Diese Funktionen nehmen keinen Startwert entgegen, sondern benutzen stattdessen automatisch den ersten bzw. den letzten Wert der Liste als Startwert. Dies kann sehr praktisch sein, etwa in folgendem Beispiel (dieser Ansatz wird in ähnlicher Form in der Methode ToString in List verwendet):

object[] pieces = new object[] { "Thing", 1, true, 5.7m };
string complete = FoldL1((r, x) => r + ", " + x, Map(x => x.ToString( ), pieces));  

Die Werte der Liste werden hier mit Trennzeichen zu einem String zusammengefügt, und die Verwendung eines separaten Startwerts würde dies unmöglich machen. Die Funktionen der Familie Fold lassen sich äußerst flexibel anwenden, und sie bilden die Basis vieler Algorithmen. Google hat ein API namens MapReduce, auf dessen Basis beliebige Algorithmen implementiert werden können, sofern sie sich als eine Kombination eines Aufrufs an Map und eines weiteren an Fold abbilden lassen. Sicherlich erfordert dies oft ein Umdenken, aber mit etwas Übung können Sie viel Zeit sparen, indem Sie Map, Filter und Fold einsetzen und damit eine wichtige algorithmische Basis wiederverwenden, statt sie neu zu programmieren.

Oliver Sturm lebt in Schottland. Er ist Microsoft MVP für C# und Program Manager für DevExpress. Zurzeit arbeitet er an seinem Buch Functional Programming in C#, das später in 2009 erscheinen wird. Sie erreichen ihn unter oliver@sturmnet.org.
Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -