© Aleksandar Jovanovic, 123RF.com

In der funktionalen Programmiersprache Haskell lässt sich bemerkenswert kompakter Code schreiben, der dennoch leicht zu lesen ist. Dieser Artikel erklärt, welche Sprachkonstrukte und -eigenschaften diese Meisterleistung ermöglichen. Eine Code-Besichtigung für Haskell-Interessierte.

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.

Weg mit dem Ballast

“Haskell programmers don’t like boilerplate” heißt es in dem online zu lesenden Buch “Real World Haskell” [3]. Dem ist nichts hinzuzufügen. Boilerplate-Code bezeichnet Codefragmente, die häufig in einem Programm auftauchen. Der Haskell-Programmierer bemüht sich solche Wiederholungen zu vermeiden. Wenn er ein Muster für eine Listenverarbeitung identifiziert, abstrahiert er darüber und bietet es als Funktion höherer Ordnung an. Funktionen, die andere Funktionen als Argumente annehmen oder zurückgeben, bezeichnet man als Funktionen höherer Ordnung. Sie geben typischerweise die Ablaufstruktur für die Verarbeitung einer Datenstruktur vor und werden über eine Funktion parametrisiert.

Da diese Funktion meist nur einmal zur Verwendung kommt und in der Regel einen kurzen Funktionskörper hat, eignet sie sich für die Schreibung als Lambda-Funktion (siehe Kasten “Lambda-Funktionen”) sowie für partielle Funktionsanwendung. Die Klassiker unter den Funktionen höherer Ordnung bilden:

map (\a -> a) [1,2,3,4] -- [1,2,3,4
map (\a -> a^2 ) [1,2,3,4] -- [1,4,9,16]
map (\a -> toUpper a) "abcd" -- "ABCD"

• »map« : Wende eine Funktion sukzessive auf alle Elemente der Liste an.
• »filter« : Filtere Elemente aus einer Liste heraus.
• Die »fold« -Funktionsfamilie: Wende eine Operation sukzessive auf jedes nächste Element der Liste und das bisherige Ergebnis der Operation an.

Damit lassen sich die Ergebnisse sehr kompakt berechnen (Abbildung 4). Die Algorithmen sind der Einfachheit halber als lokale Funktionen in der Interpreter-Shell »ghci« implementiert, was insbesondere der Lesbarkeit dient.

Abbildung 4: Map, Filter und Fold sind Klassiker der funktionalen Programmierung, von denen Haskell ausgiebig Gebrauch macht.

In einem Ausdruck der Form »makeQuad= map (^2)« bezeichnen »map« die Funktion höherer Ordnung und »(^2)« die Verarbeitungsvorschrift für die Elemente der Liste, die erst beim Aufruf der Funktion »makeQuad [1 .. 20]« verwendet wird. Die einzelnen Schritte bei der Berechnung von »foldl (+) 0 [1,2,3,4,5]« sind in Abbildung 5 dargestellt. Während die Fold-Familie die Liste durch iteratives Anwenden der Operation auf einen Wert reduziert, gibt ihr Schwager, die Funktionsfamilie Scan, die Ergebnisse aller Iterationsschritte in einer Liste aus.

Abbildung 5: Eine schrittweise Visualisierung der Funktionsweise von »foldl (+) 0 [1,2,3,4,5]«.

Das sind aber bei Weitem nicht alle Funktionen höherer Ordnung, die Haskell bietet. Sowohl die »fold« – als auch die »scan« -Funktionsfamilie gibt es in vier verschiedenen Varianten [4]. Ein paar weitere Beispiele zeigt Abbildung 6. Noch ein Wort zum Algorithmus »zipWith (\a b -> (a,b)) [1..][‘a’..’z’]« : Er verknüpft zwei Listen, indem er die Lambda-Funktion »(\a b -> (a,b))« anwendet. Der Ausdruck »[1..]« beschreibt die unendliche Liste aller natürlichen Zahlen. Die Funktion verknüpft sie mit der endlichen Liste »[‘a’..’z’]« , sodass auch der Gesamtausdruck ein Ende findet.

Abbildung 6: Von Scan bis Partition hat Haskell einige weitere Funktionen höherer Ordnung im Repertoire.

Bedarfsauswertung

Haskell ist durch und durch faul: Lazy Evaluation, zu Deutsch als Bedarfsauswertung bekannt, stellt ein Charakteristikum der Sprache dar. Sie erlaubt es, Algorithmen zu formulieren, die unendliche Datenstrukturen erzeugen, und besitzt einen weiteren bedeutenden Vorteil: Da die Datenstruktur erst dann ausgewertet wird, wenn eine Funktion ihre Elemente anfordert, spart Bedarfsauswertung häufig Zeit und auch Speicher.

Sowohl der Primzahlen- als auch der Fibonacci-Algorithmus aus Listing 1 beschreiben, wie alle Folgen der Serien berechnet werden. Die entscheidende Frage ist aber noch nicht beantwortet: Wie funktioniert der Primzahlen-Algorithmus? Das lässt sich am besten mit dem Haskell-Interpreter demonstrieren (Abbildung 7). »let sieve (x:xs) = x: sieve[ y | y <- xs, y `mod` x /= 0 ]« erklärt die lokale Funktion »sieve« , die durch den Aufruf »take 25 ( sieve[2..] )« die ersten 25 Primzahlen produziert, beginnend mit 2.

Abbildung 7: Das Sieb des Eratosthenes erzeugt einen Strom von Primzahlen.

List Comprehension

Damit bleibt noch ein unbekanntes Bausteinchen übrig: Die List Comprehension »[ y | y <- [2..], y `mod` x /= 0 ]« , die äquivalent zu »filter (\x->(x `mod` 2) == 0 ) [2..]« ist. Die List Comprehension ergibt alle Zahlen y aus »[2..]« mit der Einschränkung, dass y geteilt durch 2 null ergeben muss. Diese Formulierung zeigt deutlich, dass Haskell seine mathematischen Wurzeln nicht verleugnen kann. Die mathematische Mengenschreibweise lässt sich mit nur geringen Änderungen in Haskell verwenden:

{ n*n | n {{ELEMENT}} N , n mod 2 != 0 }
[ n*n | n <- [1..], n `mod` 2 /= 0 ]

Beide Mengen beschreiben alle Quadrate der geraden natürlichen Zahlen. Während »n*n« die Abbildung definiert, die auf jedes n angewandt wird, filtert der Ausdruck »n `mod` 2 /= 0« jedes ungerade n aus der Menge heraus. Tatsächlich ist List Comprehension, die mittlerweile auch in vielen anderen Programmiersprachen zu Hause ist, nur Syntactic Sugar, also eine vereinfachte Schreibweise, für die beiden Funktionen »map« und »filter« [1].

Nach dieser Analyse der Einzelteile gilt es, die Ergebnisse zusammenzutragen. »primes=sieve[2..]« ist durch »sieve (2:[3..]) = 2: sieve[ y | y <- [3..], y `mod` 2 /= 0 ]« definiert. Das heißt insbesondere, dass die erste Primzahl die 2 ist und »sieve« nur noch auf die natürlichen Zahlen angewandt wird, die nicht durch 2 teilbar sind. Die um die Vielfachen der 2 ausgedünnten natürlichen Zahlen müssen nun die Bedingung erfüllen, dass sie nicht durch 3 teilbar sind. Nach der 2 ist nun auch die 3 als Primzahl ermittelt.

Die Magie des Algorithmus liegt in der Bedarfsauswertung verborgen, da der Ausdruck »[2..]« nicht automatisch alle natürlichen Zahlen größer als 1 erzeugt, sondern nur so viele, wie angefordert werden. Dies ist in dem Ausdruck »sieve [ y | y <- xs, y `mod` x /= 0 ]« genau eine einzige Zahl: die nächste Primzahl. Einmal angestoßen, erzeugt der Algorithmus einen unendlichen Strom von Primzahlen, der nur mit einer endlichen Anforderung von Elementen oder einem Programmabbruch zu stoppen ist.

Dem kritischen Leser sei eingestanden, dass der vorgestellte Primzahlenalgorithmus ineffizient ist, da er natürliche Zahlen herausfiltert, die als Primzahlen nicht in Betracht kommen. Das Wiki der Haskell-Website erörtert das Berechnen von Primzahlen ausführlich [5].

Wer den Primzahlalgorithmus verstanden hat, sollte den Fibonacci-Algorithmus aus Listing 1 auch knacken können. Dieser ist deutlich anspruchsvoller als die naive Implementierung in Listing 3, besitzt dafür aber lineares statt exponentielles Laufzeitverhalten. Die ersten zwei Elemente der Liste sind mit 0 und 1 vorgegeben. Die weiteren Elemente der Liste werden auf Anfrage erzeugt und gleichzeitig zur Berechnung der neuen Elemente bereitgestellt. Dies zeigt wieder am besten die interaktive Haskell-Shell (Abbildung 8).

Abbildung 8: Der Fibonacci-Algorithmus, mit Hilfe von »zipWith« umgesetzt.

Der Ausdruck »let first20 = take 20 fib« erklärt die Liste der ersten 20 Fibonacci-Zahlen. Der entscheidende Schritt des Algorithmus ist »(zipWith (+) first20 (tail first20))« , denn dieser ermittelt die ersten 21 Elemente der Fibonacci-Zahlenreihe und entfernt dabei lediglich das erste Element. Die einzelnen Additionen in diesem Beispiel entsprechen den Iterationen in »(zipWith (+) fib (tail fib))« . Die letzten fünf Zeilen in der Abbildung zeigen exemplarisch die ersten fünf Durchgänge des Algorithmus. Eine ausführliche Diskussion der Fibonacci-Algorithmen ist wiederum im Haskell-Wiki zu finden [6].

Ein paar Worte zum verbleibenden Algorithmus »permutations« : Er basiert auf der gleichen Grundidee und löst seine Aufgabe mit Hilfe der Rekursion, da er die Berechnung an die Teilmengen delegiert und zuletzt die restlichen Elemente hinzumischt. Dabei ergibt »xs\\[x]« in »permutations« die Liste xs ohne x.

Funktionskomposition

Es bleibt mathematisch: Die Mathematik erklärt die Funktionskomposition »(f ° g)(x) = f(g(x))« dadurch, dass zuerst g auf x und anschließend f auf »g(x)« angewandt wird. Mit der Lambda-Funktion »\x -> f (g x)« , die jedem x die Funktion »f (g x)« zuordnet, lässt sich in Haskell die Funktionskomposition recht einfach definieren:

f . g = \x -> f (g x)

Die Funktionskomposition ist ein leistungsstarkes Werkzeug, um neue Funktionen zu definieren. Wer die vorgestellten Bausteine wie Pattern Matching, Rekursion, Lambda-Funktionen, partielle Funktionsanwendung, Funktionen höherer Ordnung und Bedarfsauswertung zusammenfügt, erhält mächtige Ausdrücke (Abbildung 9). Das ist Code-Wiederverwendung auf Haskell-Art.

Abbildung 9: Funktionskomposition dient der Code-Wiederverwendung auf Haskell-Art. Sie fügt mehrere Funktionen wie Bausteine zu einem großen Gebilde zusammen.

Code und Prosa

Obwohl die Komponenten der Beispiele nach der Lektüre des Artikels bekannt sein sollten, ist das Kompositum nicht so einfach zu verstehen. Am besten gelingt es, wenn man die Funktionskomposition von rechts nach links in Prosa übersetzt. So lässt sich die Anweisung »(takeWhile (<2000) . filter odd . map (^2)) [1..]« einfach formulieren als:

Wende auf den Datenstrom der natürlichen Zahlen folgende Operation an:

• Quadriere jede Zahl des Eingabestroms (»map (^2)« ),
• behalte die Ergebnisse auf dem vorherigen Schritt, die ungerade sind (»filter odd« )
• und fahre damit fort, solange die Elemente kleiner als 2000 sind (»takeWhile (<2000)« ).

Wer das nachvollziehen kann, legt gleich mit dem Programmieren los. Das Haskell-Programm aus Listing 4 gibt ein paar Titel-Statistiken zu einer Textdatei aus und ist schnell erklärt. Die »import« -Statements der ersten drei Zeilen laden explizit die Funktionen der angegebenen Bibliotheken. Die Funktion »isTitle« ermittelt für jeden String »[Char]« , ob er einen Titel darstellt oder nicht. Für den Zweck dieses Beispiels ist eine Zeichenkette genau dann ein Titel, wenn der erste Buchstabe groß und der Rest klein geschrieben ist, in Haskell: »isUpper x && all isLower xs« .

01 import Data.Char (isUpper,isLower)
02 import Data.List (sortBy)
03 import Data.Ord (comparing)
04
05 isTitle []     = False
06 isTitle (x:xs) = isUpper x && all isLower xs
07
08 main = do
09   putStrLn "The name of the input file:"
10   file <- getLine
11   inputString <- readFile file
12   let allTitles= (reverse . sortBy (comparing length) . filter isTitle) ( words inputString )
13   putStrLn ( show ( take 15 allTitles ) )
14   putStrLn ( show (length allTitles) ++ " titles in " ++ file )

»main« ist das Hauptprogramm, das über »getline« den Namen der Datei von der Konsole einliest, sodass durch »readFile file« der Inhalt der Datei in dem String »inputString« zur Verfügung steht. Die Funktionskomposition »(reverse . sortBy (comparing length) . filter isTitle) ( words inputString )« stellt die einzige Herausforderung beim Verständnis dar. »words inputString« produziert alle Wörter der Datei, die nach folgender Vorschrift weiterverarbeitet werden:

• Ermittle alle Titelwörter der Eingabeliste (»filter isTitle« ),
• sortiere die Titelwörter nach deren Länge (»sortBy (comparing length)« ),
• ändere die Sortierreihenfolge der Liste von aufsteigend nach absteigend (»reverse« ).

Zum Abschluss gibt der Code die 15 längsten Wörter (»take 15 allTitles« ) und die Anzahl der Titelwörter (»length allTitles« ) der Eingabedatei aus. Dazu muss das Programm die natürlichen Zahlen in Strings konvertieren – eine Aufgabe für die Funktion »show« . Die Quelltextdatei ist schnell kompiliert, und schon lassen sich Dateien wie »/etc/services« oder »grimm.txt« , die (ins Englische übersetzten) Märchen der Gebrüder Grimm aus der Sammlung des Gutenberg-Projekts [7], analysieren (Abbildung 10).

Abbildung 10: Das Titles-Programm extrahiert Titelwörter aus beliebigen Textdateien und gibt die 15 häufigsten aus, nach der Anzahl der Fundstellen sortiert.

Fazit

Nach ein wenig Eingewöhnung lassen sich Haskell-Ausdrücke sowohl einfach lesen als auch schreiben, da sie ihre Funktionalität prägnant auf den Punkt bringen. Nicht von ungefähr finden funktionale Elemente in letzter Zeit auch Eingang in traditionelle Programmiersprachen. So kennt C++ Funktionen höherer Ordnung, und der kommende Standard C++0x [8] führt Lambda-Funktionen ein, die das Programmieren mit der Standard Template Library deutlich effizienter machen.

Vor allem Python 3 [9] ist da schon ein paar Schritte weiter: Lambda-Funktionen, Funktionen höherer Ordnung, List Comprehension, Bedarfsauswertung – all dies ist idiomatisch, wenn es um das kompakte Verarbeiten von Daten in Python geht. Java ist zwar eine objektorientierte Programmiersprache. Es ist aber durchaus denkbar, dass die funktionale Sprache Clojure [10], die die Java-Runtime nützt, dort einspringt, wo Java Schwächen zeigt (Abbildung 11). (mhu)

Abbildung 11: Die Sprache Clojure bringt die funktionale Programmierung auf die Java Virtual Machine.