Open Source im professionellen Einsatz
Linux-Magazin 06/2011
© Aleksandar Jovanovic, 123RF.com

© Aleksandar Jovanovic, 123RF.com

Prägnante Programmierung in Haskell

Kurz und bündig

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.

803

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.

Listing 1

Kompakt implementiert

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.

Listing 2

Pattern Matching

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.

Listing 3

Rekursion

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.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 6 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Funktionale Programmierung (1): Grundzüge

    Ob Microsofts F# oder neue Features in C++, Java und Python: Der funktionale Programmierstil macht wieder Schlagzeilen. Mit diesem Online-Artikel beginnt Linux-Magazin Online eine kleine Reihe zur funktionalen Programmierung. In der ersten Folge beschreibt unser Autor Rainer Grimm die Grundzüge dieses Programmierparadigmas. Kommende Folgen widmen sich der funktionalen Programmierung in Python und dem Framework MapReduce von Google.

  • Bücher

    Passend zum Haskell-Artikel in dieser Ausgabe bespricht das Linux-Magazin zwei Bücher über die funktionale Programmiersprache. Das erste ist auf Deutsch erschienen und kommt als Intensivkurs schnell zur Sache, das zweite ist englischsprachig und besticht durch seine Originalität.

  • Bücher

    Die Bücherseite stellt dieses Mal Bücher für fortgeschrittene Programmierer vor. Der erste Titel beschäftigt sich mit der Python-Praxis, der zweite mit Parallelprogrammierung in der Sprache Haskell.

  • Rest ist ein REST-Framework für Haskell

    Mit Rest hat Adam Bergmark ein quelloffenes REST-Framework für die funktionale Programmiersprache Haskell angekündigt.

  • School of Haskell im Betatest

    Das auf Haskell und funktionale Programmierung spezialisierte Unternehmen FP Complete hat die Beta-Phase seiner Online-Lernplattform School of Haskell gestartet.

comments powered by Disqus

Ausgabe 11/2017

Digitale Ausgabe: Preis € 6,40
(inkl. 19% MwSt.)

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.