Haskell (Programmiersprache)

Haskell
Basisdaten
Entwickler	Paul Hudak, Lennart Augustsson, John Hughes, Simon Peyton Jones, Erik Meijer, Philip Wadler
Erscheinungsjahr	1990
Aktuelle Version	Haskell 98
Betriebssystem	Windows, Linux, Mac OS X, uvm.
Kategorie	Funktionale Programmiersprache
deutschsprachig	nein
www.haskell.org

Haskell ist eine funktionale Programmiersprache, benannt nach dem US-amerikanischen Mathematiker Haskell Brooks Curry, dessen Arbeiten zur mathematischen Logik eine maßgebliche Grundlage heutiger funktionaler Programmiersprachen bilden.

Haskell ist eine standardisierte und statisch typisierte Programmiersprache, die Bedarfsauswertung (engl. lazy evaluation) sowie polymorphe Datentypen unterstützt.

Haskell wurde in den 1980er Jahren mit der Motivation entwickelt, die funktionale Programmierung durch die Einführung einer standardisierten, modernen Sprache zu vereinheitlichen. Die aktuelle Version des Sprachstandards liegt unter dem Namen Haskell 98 vor. Haskell bietet sich zur Entwicklung einer großen Bandbreite von Anwendungen an und eignet sich insbesondere auch als Spezifikations- und Lehrsprache. Als funktionale Programmiersprache verspricht Haskell eine hohe Entwicklungsproduktivität sowie kurzen und potentiell gut wartbaren Quellcode.

Entscheidend dafür ist das Konzept der referenziellen Transparenz. Dieses besagt, dass eine Funktion von überall im Program aufgerufen werden kann und bei gleichen Argumenten immer das gleiche Ergebnis zurückliefern wird. Es gibt also keine Funktion die eine Wirkung hervorruft. Damit wird sicher gestellt, dass eine Funktion in jeder Umgebung immer das Ergebnis liefert, welches der Programmierer von ihr erwartet. Insbesondere gibt es keine parameterlosen Funktionen, die bei jedem Aufruf einen anderen Wert zurück liefern.

Zum Beispiel gibt es daher keine Funktion wie getChar im herkömmlichen C-Style, da diese nicht referenziell transparent wäre: denn jedesmal wäre der Rückgabewert abhängig von der Eingabe des Benutzers auf der Tastatur. Das wirft natürlich das Problem der Kommunikation mit der Betriebssystemumgebung auf, welches durch das Konzept der Monade umgangen wird. Im Fall der Kommunikation mit der Betriebssystemumgebung wird die IO-Monade benutzt.

Bei der Monade wird eine lineare Abfolge von Funktionsaufrufen in geschachtelte Aufrufe übersetzt. Dabei erhält die erste Funktion den Aufruf der zweiten Funktion als Parameter, die wiederum die dritte Funktion als Parameter erhält. Dies setzt sich fort. Die sich ändernde Umgebung wird nun als Einheit und Teil des Kontexts der aufrufenden Funktion betrachtet. Das heißt vor dem Aufruf von getChar enthält die Umgebung ein Zeichen, die Funktion nach getChar startet in einer Umgebung ohne.

Sprachkonstrukte aus Haskell wurden auch in die Programmiersprache Python übernommen.

Beispiele

Fakultät

Die klassische Definition der Fakultätsfunktion:

 fac 0 = 1
 fac n = n * fac (n - 1)

Eine elegante Definition, die Haskells Notation für Listen benutzt:

 fac n = product [1..n]

Fibonacci

Die naive Implementierung der Fibonacci-Funktion:

 fib 0 = 0
 fib 1 = 1
 fib n = fib (n - 2) + fib (n - 1)

Eine schnelle Implementierung der selben Funktion:

 fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

Diese Definition erzeugt eine unendliche Liste und faltet diese mit der zipWith-Funktion. Unendliche Datenstrukturen können dank lazy evaluation in Haskell elegant dargestellt werden.

QuickSort

Der QuickSort-Algorithmus, formuliert in Haskell:

 qsort []     = []
 qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]

Die erste Zeile gibt an, dass die Funktion auf eine leere Liste angewendet wieder eine leere Liste ergeben soll. Die zweite Zeile sortiert rekursiv nicht-leere Listen: das erste Element x wird als mittleres Element der Ergebnisliste verwendet. Davor werden sortiert alle kleineren, dahinter alle größeren Elemente eingeordnet. Listenbeschreibungen werden dazu verwendet, aus der Restliste xs alle kleineren bzw. größeren Elemente als x auszuwählen.

Wie man es von Quicksort erwartet, besitzt auch diese Implementierung eine mittlere asymptotische Laufzeit von $O(n\cdot \log n)$ und eine worst-case Laufzeit von $O(n^{2})$. Im Gegensatz zur geläufigen Implementierung in einer imperativen Sprache arbeitet qsort jedoch nicht in-place.

Weblinks

• http://www.haskell.org/
• http://www.informatik.uni-bonn.de/~ralf/teaching/Hskurs_toc.html (deutsch)
• http://haskell.readscheme.org/

Literatur

• Thompson, Simon: Haskell - The Craft of Functional Programming, 1999, Addison-Wesley, ISBN 0201342758

• Why Functional Programming Matters by John Hughes, The Computer Journal, Vol. 32, No. 2, 1989, pp. 98 - 107. [1] Vorteile funktionaler Programmierung. Zeigt Formen der Modularisierung, die wesentlich auf Funktionen höherer Ordnung und Bedarfsauswertung beruhen.