Parameter Akkumulation

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ...

Übersicht: Parameter Akkumulation

Idee

Beispiel: flatten

Idee

Die Idee der Parameter Akkumulation ist es, einen zusätzlichen Parameter in Funktionen einzusetzen, um Zwischenergebnisse effizient zu verarbeiten. Diese Technik wurde schon in der Funktion reverse2 genutzt. Häufig können mit der Parameter Akkumulation "teure" Konkatenationsoperationen ("++") vermieden werden.

[ nach oben ]

Beispiel: flatten

Das Glätten eines binären Baumes wurde bereits im Kapitel 6 (Bäume) besprochen. Zur Erinnerung unsere erste Definition für flatten.

 01  flatten			:: Btree a -> [a]

 02  flatten (Leaf x)		= [x]

 03  flatten (Fork xt yt)	= flatten xt ++ flatten yt

Die Arbeitsweise dieser Funktion ist simpel. Der Baum wird traversiert, zuerst wird in den linken Teilbaum verzweigt, dann in den rechten. Gelangt man an ein Blatt wird eine ein-elementige Liste angelegt. Diese Teillisten werden am Ende der Rekursion über die ++-Operation konkateniert. Wir führen nun einen zusätzlichen Parameter ein, um den letzten Schritt des Algorithmus - die Konkatenation - zu vermeiden.

 01  flatcat			:: Btree a -> [a] -> [a]

 02  flatcat xt xs		= flatten xt ++ xs

Es gilt also flatcat xt [] = flatten xt.

Transformieren wir flatcat in eine rekursive Struktur ohne Referenz auf flatten.

 01  flatcat			:: Btree a -> [a] -> [a]

 02  flatcat (Leaf x) xs	= x : xs

 03  flatcat (Fork xt yt) xs    = flatcat xt (flatcat yt xs)

flatcat steigt rekursiv in den rechten und linken Teilbaum ab. Wichtig ist, dass nun zuerst das rechteste Blatt bearbeitet wird, da wir in der Ergebnisliste (xs) die Elemente vorne anfügen. Um die Effizienz unserer Definitionen bewerten zu können führen wir eine Laufzeitanalyse durch.

Laufzeitanalyse für flatten.
```
T(flatten)(0)		= O(1)
```
```
T(flatten)(h+1)		= 2 T(flatten)(h) + T(++)(2^h,2^h)
```
Aus Induktion folgt:
```
T(flatten)(h)		= Θ(h 2^h)
```
flatten benötigt also Θ(s log s) Schritte auf einem Baum der Größe s (mit s = 2^h). Exemplarisch folgt nun der Induktionsbeweis für T(flatten). Fast jede Laufzeitanalyse lässt sich durch eine analoge Beweisführung darstellen.
Laufzeitanalyse für flatcat.
```
T(flatcat)(0,n)		= O(1)
```
```
T(flatcat)(h+1,n)	= O(1) + T(flatcat)(h,2^h+n) + T(flatcat)(h,n)
```
Aus Induktion folgt:
```
T(flatcat)(h,n)		= Θ(2^h)
```
flatcat benötigt lineare Laufzeit im Verhältnis zur Baumgröße. n ist ist die Länge der Ergebnisliste und folglich für die Laufzeitberechnung bedeutungslos.

Es ist deutlich zu erkennen, dass sich der Vorgang der Parameter Akkumulation an einem Schema orientiert. Ausgehend von einer intuitiven Lösung für ein Problem wird systematisch über eine Hilfsfunktion eine effizientere Definition entwickelt.

[ nach oben ]

... [ Seminar "Einführung in die funktionale Programmiersprache Haskell" ] ... [ Inhaltsverzeichnis ] ... [ zurück ] ... [ weiter ] ... [ nach oben ] ...