Faltungen

Datenbanken kennen Aggregatfunktionen. Ein Aggregat ist - Ja? - leider daneben! Ein Aggregat ist eine Anhäufung. Im Grunde ist die ehrfurchtsgebietende Miene, mit der ein Heizungsfachman ein elektronisches Kästchen aus einer Packung holt, während er dieses als Aggregat bezeichnet um es darauf in die kaputte Heizung einzubauen, eher lachhaft. Würde er sagen, er baue jetzt einen elektronischen Haufen in die Heizung ein, würden wir eher grinsen als ehrfürchtig Abstand haltend sein fachmännisches Tun zu würdigen.

Mit Aggregat ist also gemeint, dass wir etwas unübersichtiches zu einem Haufen zusammenwerfen, um den Überblick zu behalten. Etwas vornehmer nennt man diesen Vorgang manchmal auch Faltung.

Beispiele bei Datenbanken sind zum Beispiel COUNT(*) für die Anzahl der Elemente, AVG(*) für deren Durchschnitt und SUM(*) die Summe aller Elemente.

Was mich immer schon geärgert hat ist, ist, das zumindest bei Datenbankten kein offensichtlicher Weg existiert, solche “Aggregatfunktionen” selber zu definieren. Mag sein, daß einzelne dieser Datenbanken solche Möglichkeiten haben. In der SQL’92 Spezifikation sind Aggregatfunktionen vorgegbene schwarze Kisten, die man benutzen kann. Sonst nichts.

Das Wesen einer Aggregatfunktion oder Faltung ist, eine Liste “zusammenzufalten”, sodaß man Ende der Operation ein einzelnes etwas (etwa eine Summe) anstatt einer unhandlichen Liste hat.

Wie kommt man zu einer Aggregatfunkion? Aus der Operation z(a,b)=a+b gelang man zu der Aggregatfunktion SUM(*)  aus der Operation z(n,a)=n+1 gelangt man zu Aggregatfunktion COUNT(*) und anderes mehr. Jeder Programmieranfänger hat schonmal eine Aggregation programmiert, ohne sich darüber Gedanken gemacht zu haben. Dazu ist der Vorgang auch insgesamt zu banal. Zumeist wird man wohl eine FOR-Schleife verwendet haben. Das ist sehr schön. aber nicht unser Thema. gesucht ist eine Generalisierung dieses Vorgangs. Das bedeutet, daß wir die gesamte Faltung von dem konkreten Faltungsoperator abstrahieren müssen.

Angenommen, wir haben eine Liste L=(x1,x2,..xn) sowie eine zweistellige Faltungsoperation z. Dann ist die Faltung f eine Funktion höherer Ordnung mit dem Faltungsoperator z und der Liste L als Argumenten:

f(z,L) = z( L[0] , L[1] )           falls die Liste zweielementig ist und
z( L[0] , f(z, L[1..n])              sonst

Beispiel:

z(a,b)=a+b und L=[4,3,2,6]

Dann ist

f(z,L)=
4+f(z,[3,2,6])=
4+3+f(z,[2,6])=
4+3+2+6=15.

Schönheitsfehler ist noch, daß unsere Konstruktion nur mit mindestens zweielementigen Listen arbeitet. Dem kann man mit einem zusätzlichen Startparameter s begegnen, mit dem das erste Listenelement verknüpft wird.

Dann kommt man zu folgender Version:

f(s,z,L) = s    falls die Liste leer ist,
z( L[0] , f(s,z, L[1..n])    sonst.

In Perl kann das so aussehen:

sub foldleft ($&@) {
  my ($s,$z,@l)=@_;
  return $s unless @l;
  my $a = shift @l;
  return $z->($a,foldleft($s,$z,@l));
}

Schöner und schneller ist aber diese iterative Version:

sub foldl ($&@) {
  my ($s,$z,@l) = @_;
  $s = $z->($s,$_) for (@l);
  return $s
}

Wozu das gut ist? Ganz einfach: Durch Konstruktionen wie diese spart man innere Schleifen. Um nun die Summe aller Elemente einer Liste zu bilden, kann man

$summe = foldl 0, sub {$_[0]+$_[1]}, @LISTE

schreiben.

Um alle Zeilen einer Datei zusammenzufassen und dabei zwischen je zwei Zeilen eine Leerzeile einzubauen:

$text =  foldl 0, sub {$_[0] . "\n". $_[1]}, <FILE>;

Anstatt hier fehleranfällig mit Schleifen und Variablen zu arbeiten, kann man eine einzige Funktion aufrufen. Funktionale Programmiersprachen wie Haskell und andere haben eine solche Faltungsfunktion direkt mit eingebaut. Interessant ist auch, daß große Teile der Programmentwicklung sich gerade mit Aggregationen befassen, auch wenn uns das nicht immer bewusst ist. Wer als Programmierer ein bisschen darüber nachdenkt, was er gerade tut, stößt täglich selbst auf Beispiele. Jeder Erstellung einer HTML-Seite aus einer Datenbankabfrage ist  ein solches Beispiel.

Tags: Aggregation, Faltung, Fold, Perl