Prägnante Programmierung in Haskell

Haskell, die rein funktionale Programmiersprache, soll kompakteres und eleganteres Programmieren erlauben, als es traditionelle imperative Programmiersprachen wie C/C++, Java oder auch Python möglich machen. Eine Stufe abstrakter formuliere die Sprache Algorithmen, behaupten ihre Fans. Wie das im Detail aussieht, zeigt dieser Artikel: Programmieren in Haskell ist das Programmieren auf einer höheren Ebene.

Das Sieb des Eratosthenes (»sieve« ) in Listing 1 ist ein alter Bekannter aus Schule und Uni [1], der sich in Haskell äußerst prägnant auf den Punkt bringen lässt. Der Fibonacci-Algorithmus »fib« und der Permutationsalgorithmus »permutations« im selben Listing sind zwei von vielen weiteren Beispielen, die die Ausdruckskraft von Haskell eindrucksvoll belegen.

01 import Data.List
02
03 -- Sieb des Eratosthenes
04 primes = sieve[2..]
05 sieve (x:xs) = x: sieve[ y | y <- xs, y `mod` x /= 0 ]
06
07 -- Fibonacci-Algorithmus
08 fib = 0 : 1 : (zipWith (+) fib (tail fib))
09
10 -- Permutation
11 permutations [] = [[]]
12 permutations xs = [ x:ps | x <- xs , ps <- permutations ( xs\\[x] ) ]

Zugegeben, für das imperative Auge sind diese Algorithmen, die auf Pattern Matching, Rekursion, partieller Funktionsanwendung [2], Funktionen höherer Ordnung und Bedarfsauswertung basieren, nicht einfach zu lesen. Zumal die Funktionskomposition die Bausteine zu noch leistungsstärkeren Gebilden verknüpft. Aber die Ergebnisse sind vielversprechend. Abbildung 1 zeigt ein weiteres Charakteristikum von Haskell-Programmen, das nicht unerwähnt bleiben soll: Sowohl das Sieb des Eratosthenes als auch der Fibonacci-Algorithmus in Listing 1 erzeugen unendliche Listen. Die Funktion »take« fordert aber nur endlich viele Elemente an. Auf ein einzelnes Element der Liste kann der Programmierer mit dem Indexoperator »!!« zugreifen.

Abbildung 1: Ein erster Eindruck von Haskell zeigt kompakte Algorithmen in Aktion.

Wie funktionieren diese Beispiele? Eine steile Lernkurve beginnt: Damit die vollständigen Ausdrücke verständlich werden, erklärt dieser Artikel deren Bausteine im Detail.

Pattern Matching

Der Permutationsalgorithmus in Listing  1 verwendet Pattern Matching, um abhängig von der Länge der Eingabeliste die richtige Aktion auszuführen. Pattern Matching entspricht der Case-Struktur der imperativen Programmierung, ist aber deutlich mächtiger. Ein paar einfache Beispiele: Die Funktionen »neg« , »getSecond« , »sum« und »isTitle« in Listing  2 wenden verschiedene Varianten an. Die Regeln sind schnell erklärt: Das erste Pattern, das den Argumenten entspricht, kommt zur Verwendung.

Pattern Matching lässt sich sowohl auf explizite Werte wie in »neg True« als auch auf positionale Argumente wie in »getSecond (_,b,_)« anwenden. Dabei steht der Unterstrich »_« in dem Pattern für einen Platzhalter (Abbildung 2). Kommen Listen als Argumente zum Einsatz, so bezeichnet »[]« die leere Liste und »(x:xs)« die nicht-leere Liste. Genauer: Der Haskell-Programmierer greift auf das erste Element der Liste mittels »x« zu, auf den Rest der Liste mit »xs« .

Abbildung 2: Pattern Matching hilft bei der Arbeit mit positionalen Argumenten und Listen.

Rekursion

Pattern Matching, bei dem es je eine Regel für die leere Liste und für die Liste mit einem Element gibt, kommt in Haskell typischerweise zusammen mit Rekursion zum Einsatz. Die Funktion »sumList« in Listing 2 beispielsweise wertet in dem Pattern »sumList (x:xs)= x + sumList xs« das erste Element aus und wendet »sumList« rekursiv auf dem Rest der Liste an. Da es charakteristisch für Haskell ist, eine Aktion auf dem ersten Element einer Liste und auf dem Rest der Liste zu definieren, sprechen Haskell-Programmierer nur noch vom »head« beziehungsweise »tail« einer Liste. Die Rekursion über »sumList« beendet sich genau dann, wenn der Rest der Liste nur noch die leere Liste »[]« ist.

01 neg True = False
02 neg False= True
03
04 getSecond (_,b,_) = b
05
06 sumList [] = 0
07 sumList (x:xs) = x + sumList xs
08
09 isTitle []     = False
10 isTitle (x:xs) = isUpper x && all isLower xs

Wer bei Rekursion gewöhnt ist, auf den bekannten Stack-Overflow-Fehler zu warten, dem sei versichert, dass der Haskell-Compiler für die Rekursion optimiert ist. Konkret heißt dies, dass endrekursive Aufrufe in Haskell einen konstanten Speicherplatzbedarf besitzen.

Listing 3 zeigt ein paar einfache Algorithmen, die auf Rekursion basieren. In Abbildung 3 sind die Funktionen in Aktion zu sehen. Bemerkenswert an der Funktion »mult« ist, dass sie in der Zeile 13 ohne Multiplikation auskommt. Stünde hier schlicht »mult n m = m * n« , dann würde sie Multiplikation durch Multiplikation definieren. Doch auf »mult n (m -1 )« wird so lange Pattern Matching angewandt, bis es zur Addition »n + n + n + n + n + n + n« entrollt ist.

01 fak 0 = 1
02 fak 1 = 1
03 fak n = n * fak (n - 1)
04
05 lengthList []= 0
06 lengthList (x:xs)= 1 + lengthList xs
07
08 reverseList [] = []
09 reverseList (x:xs) = reverseList xs ++ [x]
10
11 mult n 0 = 0
12 mult n 1 = n
13 mult n m = (mult n (m - 1)) + n
14
15 fib 0 = 0
16 fib 1 = 1
17 fib n = fib(n-2) + fib(n-1)

Abbildung 3: Die hier eingesetzten Funktionen verwenden Rekursion.