Haskell ist eine rein funktionale Programmiersprache, benannt nach dem US-amerikanischen Mathematiker Haskell Brooks Curry, dessen Arbeiten zur mathematischen Logik eine Grundlage funktionaler Programmiersprachen bilden. Haskell basiert auf dem Lambda-Kalkül, weshalb auch der griechische Buchstabe Lambda als Logo verwendet wird. Die wichtigste Implementierung ist der Glasgow Haskell Compiler (GHC).
Haskell | |
---|---|
Basisdaten | |
Paradigmen: | funktional, nicht-strikt, modular, deklarativ |
Erscheinungsjahr: | 1990 |
Designer: | Lennart Augustsson, Warren Burton, Kevin Hammond, Paul Hudak, John Hughes, Thomas Johnsson, Simon Peyton Jones, John Launchbury, Erik Meijer, Alastair Reid, Philip Wadler |
Entwickler: | Simon Peyton Jones, Paul Hudak, Philip Wadler, et al. |
Aktuelle Version | Haskell 2010 (Juli 2010) |
Typisierung: | statisch, stark, Typinferenz |
Wichtige Implementierungen: | GHC, Hugs, NHC, JHC, Yhc |
Dialekte: | Helium, Gofer |
Beeinflusst von: | APL, LISP, Miranda, ML, C++ |
Beeinflusste: | Agda, Cayenne, Clean, Curry, Idris, Python, Rust, Scala, C#, F#, Swift, JavaScript |
Betriebssystem: | Microsoft Windows, Unix-ähnliches System |
haskell.org |
Entwicklung Bearbeiten
Gegen Ende der 1980er Jahre gab es bereits einige funktionale Programmiersprachen. Um der Wissenschaft eine einheitliche Forschungs- und Entwicklungsbasis bereitzustellen, sollte eine standardisierte und moderne Sprache die funktionale Programmierung vereinheitlichen. Zunächst wollte man dazu Miranda als Ausgangspunkt benutzen; doch deren Entwickler waren daran nicht interessiert. So wurde 1990 Haskell 1.0 veröffentlicht.
Die Sprachderivate von Haskell sind zahlreich; dazu zählen Parallel Haskell, Distributed Haskell (ehemals Goffin), Eager Haskell, Eden mit einem neuen Ansatz zum parallelen Programmieren und Bedarfsauswertung, DNA-Haskell und sogar objektorientierte Varianten (Haskell++, O’Haskell, Mondrian). Des Weiteren diente Haskell beim Entwurf neuer Programmiersprachen als Vorlage. So wurde beispielsweise im Falle von Python die Lambda-Notation sowie Listenverarbeitungssyntax übernommen.
Eigenschaften Bearbeiten
Programmfluss Bearbeiten
- Haskell ist eine rein funktionale Programmiersprache. Funktionen geben nur Werte zurück, ändern aber nicht den Zustand eines Programms (d. h. Funktionen haben keine Nebeneffekte). Das Ergebnis einer Funktion hängt deshalb nur von den Eingangsparametern ab, und nicht davon, wann oder wie oft die Funktion aufgerufen wird.
- Es gibt keine imperativen Sprachkonstrukte. Durch Monaden ist es möglich, Ein- und Ausgabeoperationen und zustandsabhängige Berechnungen wie Zufallsgeneratoren rein funktional zu behandeln.
- Es gibt keine Operationen, die einen Variablenwert verändern. So gibt es auch keine Unterscheidung zwischen Variablen und Konstanten und man braucht keine
const
-Attribute oder Literal-Makros wie in C++ oder in C. - Zwischen Identität und Gleichwertigkeit von Objekten wird nicht unterschieden.
- Da Nebeneffekte fehlen, sind Programmbeweise beträchtlich einfacher.
- Haskell ist nicht-strikt. Es werden nur Ausdrücke ausgewertet, die für die Berechnung des Ergebnisses gebraucht werden.
first x y = x quadrat x = x * x
Typsystem Bearbeiten
- Haskell ist stark typisiert. Es wird also zum Beispiel streng zwischen Wahrheitswerten, Zeichen, ganzen Zahlen, Gleitkommazahlen und Funktionen von und zu verschiedenen Typen unterschieden.
- Haskell erlaubt Typvariablen. Damit können Funktionen sehr allgemein formuliert werden. Wird eine allgemeingehaltene Funktion für bestimmte Typen verwendet, werden automatisch die Typen abgeglichen (Typinferenz).
map :: (a -> b) -> [a] -> [b]
map toUpper :: [Char] -> [Char]
- Haskell ist von der Grundidee her statisch typisiert, obwohl es auch Erweiterungen für dynamische Typen gibt. Das bedeutet, dass für die meisten Berechnungen die Typen bereits zum Zeitpunkt der Programmübersetzung feststehen. Dies deckt viele „offensichtliche“ Fehler noch vor Ausführung des Programms auf.
- Haskell unterstützt Funktionen höherer Ordnung (Funktionale). Das sind Funktionen, die Funktionen als Eingabeparameter bzw. Funktionen als Ergebnis haben. Ein Beispiel ist die
map
-Funktion, die eine Funktionf
auf jedes Element eines Datentyps (hier Liste) anwendet.
map :: (a -> b) -> [a] -> [b] map f [] = [] map f (x:xs) = f x : map f xs map quadrat [1,2,3] = [quadrat 1, quadrat 2, quadrat 3] = [1,4,9]
- Funktionen erlauben Currying. Während man in anderen Sprachen Tupel als Argumente an Funktionen übergibt, also Funktionstypen der Form
(a, b) -> c
verwendet, ist in Haskell die Curry-Forma -> b -> c
üblicher. Damit wird die partielle Auswertung von Funktionen bequem möglich. Der Ausdruckmap toUpper
ist beispielsweise eine teilweise Auswertung vonmap
, denn er beschreibt eine Funktion, nämlich die Funktion, welche alle Kleinbuchstaben einer Liste in Großbuchstaben verwandelt. - Haskell erlaubt benutzerdefinierte Datentypen. Diese algebraischen Datentypen werden mit Hilfe von Datenkonstruktoren definiert.
data Tree = Leaf Int | Branch Int Tree Tree
data Tag = Montag | Dienstag | Mittwoch | Donnerstag | Freitag | Samstag | Sonntag deriving (Show, Eq, Ord, Ix, Enum)
- Haskell unterstützt Typenklassen. Mit Typenklassen lassen sich Typen zusammenfassen, welche eine bestimmte Menge an Operationen unterstützen. In Signaturen von Funktionen dürfen als Abstufung zwischen festen Typen wie
Char
und freien Typvariablen auch noch Typvariablen mit Einschränkung auf bestimmte Klassen verwendet werden.
- In Haskell haben Ein- und Ausgabefunktionen einen speziellen Typkonstruktor namens
IO
.
putStrLn :: String -> IO () getLine :: IO String
Syntax Bearbeiten
Haskell unterscheidet Groß- und Kleinschreibung. Bezeichner, die mit einem Großbuchstaben beginnen, stehen für Typ- und Wertkonstruktoren. Bezeichner, die mit einem Kleinbuchstaben beginnen, stehen für Typvariablen, Funktionen und Parameter.
Der Umgang mit Leerzeichen und Zeilenumbrüchen geschieht in Anlehnung an das intuitive Verständnis von mathematischer Notation, bei Zeilenumbrüchen muss lediglich eine Einrückung beliebiger Tiefe geschehen, damit der Zusammenhang nicht verlorengeht. So ist der Ausdruck
fun a b = a*b
völlig gleichwertig zu
fun a b= a * b
Haskell unterstützt einzeilige und mehrzeilige Kommentare, erstere ab den Zeichen --
bis zum Ende der Zeile und letztere im Einschluss von {-
und -}
.
f x = x**2 -- f y = y*5 diese Zeile ist auskommentiert {- Alles, was hier drin steht, wird auch nicht beachtet. f z = z*2 -}
Haskell bietet eine Reihe von syntaktischen Besonderheiten. Diese sollen nicht darüber hinwegtäuschen, dass alles rein funktional erklärt ist.
- Die
do
-Notation verleiht Berechnungen mit Monaden das Aussehen von imperativen Programmen.
Statt
readFile "eingabe.txt" >>= writeFile "ausgabe.txt"
readFile "eingabe.txt" >>= (\inhalt -> writeFile "ausgabe.txt" inhalt)
do inhalt <- readFile "eingabe.txt" writeFile "ausgabe.txt" inhalt
- Sowohl symbolische Bezeichner (bestehend etwa aus +, -, *, /, >, <) als auch alphanumerische Bezeichner (Buchstaben, Ziffern und Apostroph) können für Funktionsnamen verwendet werden und sowohl als Infix-Operatoren als auch in Präfixschreibweise eingesetzt werden. Es gilt beispielsweise
a + b = (+) a b a `div` b = div a b
- Haskell erlaubt spezielle Notationen bei der Listenverarbeitung. So können unter anderem Zahlenfolgen mit zwei Punkten (
..
) angedeutet werden:
[0..5] = [0,1,2,3,4,5] ['a'..'e'] = ['a','b','c','d','e'] = "abcde" [0,2..10] = [0,2,4,6,8,10]
[1..] = [1,2,3 usw.] [10,20..] = [10,20,30 usw.]
[ x | x <- [1..], even x]
do x <- [1..] guard $ even x return x
[x | odd x]
Programmierung Bearbeiten
- Haskell erlaubt Mustervergleiche (engl. pattern matching). So nennt man die Verwendung von Konstruktortermen als formale Parameter. Dabei sind die Parameterterme die Muster (engl. pattern) der Funktionsargumente.
fak :: Integer -> Integer fak 0 = 1 fak n = n * fak (n-1)
Module Bearbeiten
Zu Haskell gehört auch ein Modulsystem. Der Haskell-98-Standard definiert eine Grundmenge von Modulen, die ein standardkonformes Haskell-System zur Verfügung stellen muss. Beispielsweise ein Modul, welches Ein- und Ausgabe-Funktionen bereitstellt oder ein Modul, welches Funktionen auf Listen implementiert.
Um Module nutzen zu können, muss man sie importieren. Dies geschieht mithilfe des import
-Befehls.
import List import Maybe
In verschiedenen Modulen können Funktionen und Typen die gleichen Namen besitzen. Diese Bezeichner können unterschieden werden,
- indem nur einer der Bezeichner importiert wird,
import Data.List(delete) x = delete 'a' "abc"
- oder indem die Bezeichner qualifiziert, also durch Verbinden mit dem Modulnamen eindeutig gemacht werden.
import qualified Data.List x = Data.List.delete 'a' "abc"
- oder
import qualified Data.List as List x = List.delete 'a' "abc"
Ebenfalls möglich, aber nicht empfohlen ist das Ausblenden von Bezeichnern beim Importieren mit hiding
.
Beispiele Bearbeiten
Fakultät Bearbeiten
Eine elegante Definition der Fakultätsfunktion, die Haskells Notation für Listen benutzt:
fac :: Integer -> Integer fac n = product [1..n]
Oft wird aber auch rekursiv gearbeitet:
facr :: Integer -> Integer facr 0 = 1 facr n = n * facr (n-1)
Endrekursion ist dabei oftmals effizienter, aber auch aufwendiger zu schreiben:
facrt :: Integer -> Integer facrt n = _facrt n 1 where _facrt 0 r = r _facrt n r = _facrt (n-1) (r*n)
Diesen Schreibaufwand kann man jedoch reduzieren. In _facrt enthält der Parameter r das jeweilige (Zwischen-)Resultat. Zu Beginn der Iteration wird r auf den Startwert gesetzt. Bei jedem Iterationsschritt wird das neue Zwischenergebnis mit einer bestimmten Funktion aus dem bisherigen Zwischenresultat und n berechnet. Zum Schluss wird r als Endergebnis zurückgegeben. Dieses Prinzip kann man durch eine wiederverwendbare Funktion recur ausdrücken:
recur :: (Num a, Eq a) => (b -> a -> b) -> b -> a -> b recur f r 0 = r recur f r n = recur f (f r n) (n-1)
Unter Verwendung von recur kann man die Fakultätsfunktion mit Endrekursion dann sehr kompakt schreiben:
facrg :: Integer -> Integer facrg = recur (*) 1
Fibonacci Bearbeiten
Eine einfache Implementierung der Fibonacci-Funktion:
fib :: Integer -> Integer fib 0 = 0 fib 1 = 1 fib n = fib (n - 2) + fib (n - 1)
Eine schnelle Implementierung der Folge:
fibs :: [Integer] fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))
tail
entfernt das erste Element aus einer Liste, zipWith
kombiniert zwei Listen elementweise mithilfe einer weiteren Funktion (hier (+)
). Die Definition entspricht einer Fixpunktgleichung. Dass die Definition stimmt, überprüft man am schnellsten, indem man sich vorstellt, dass fibs
bereits fertig berechnet vorliegt. Als Nächstes muss man sich noch überlegen, dass die Definition auch ausgewertet werden kann. Die ersten beiden Glieder von fibs
sind unmittelbar klar: 0 und 1. Für das Berechnen jedes weiteren Gliedes muss aber nur auf bereits berechnete Glieder von fibs
zurückgegriffen werden. Die Bedarfsauswertung führt dazu, dass die Folge fibs
tatsächlich elementweise berechnet wird.
Man könnte auch sagen, dass fibs
ein Fixpunkt der Funktion \xs -> 0 : 1 : (zipWith (+) xs (tail xs))
ist. Das wiederum lässt sich in Haskell direkt notieren als
fix (\xs -> 0 : 1 : (zipWith (+) xs (tail xs)))
Differenzengleichung Bearbeiten
Man kann auf diese Weise sehr elegant Differentialgleichungen bezüglich Potenzreihen oder Differenzengleichungen bezüglich Zahlenfolgen formulieren und gleichzeitig lösen.
Angenommen, man möchte die Differentialgleichung y'(x) = f(x, y(x)) bezüglich y in Form einer Zeitreihe lösen, also einer Liste von Zahlen. Durch diese Diskretisierung wird die Differentialgleichung zur Differenzengleichung. Statt eines Integrals berechnen wir Partialsummen. Die folgende Funktion hat als Parameter die Integrationskonstante und eine Zahlenfolge.
integrate :: Num a => a -> [a] -> [a] integrate = scanl (+)
scanl
akkumuliert die Werte einer Folge mit Hilfe einer anderen Funktion, hier (+)
, und gibt die Liste der Akkumulatorzustände zurück.
Damit kann man bereits das explizite Eulerverfahren für die Schrittweite 1 implementieren. x0
und y0
sind hierbei die Anfangswerte. Der Apostroph hat keine eigenständige Bedeutung, er ist Teil des Namens y'
.
eulerExplicit :: Num a => (a -> a -> a) -> a -> a -> [a] eulerExplicit f x0 y0 = let x = iterate (1+) x0 y = integrate y0 y' y' = zipWith f x y in y
Diese Funktionsdefinition besteht also im Wesentlichen aus der Feststellung, dass y
das Integral von y'
mit Anfangswert y0
ist, (oder umgekehrt, y'
die Ableitung von y
) und aus der eigentlichen Differentialgleichung y' = zipWith f x y
. Weil man hierbei den Algorithmus eher in der Form der Aufgabenstellung als in Form eines Lösungsweges notiert, spricht man hierbei von deklarativer Programmierung.
Quicksort Bearbeiten
Der Quicksort-Algorithmus, formuliert in Haskell:
qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort kleinergl ++ [x] ++ qsort groesser where kleinergl = [y | y <- xs, y <= x] groesser = [y | y <- xs, y > x]
Die erste Zeile definiert die Signatur von Quicksort. Die zweite Zeile gibt an, dass die Funktion auf eine leere Liste angewendet wieder eine leere Liste ergeben soll. Die dritte Zeile sortiert rekursiv nicht-leere Listen: das erste Element x
wird als mittleres Element der Ergebnisliste verwendet. Davor werden alle nicht-größeren sortiert, dahinter alle größeren Elemente eingeordnet. Listenbeschreibungen werden dazu verwendet, aus der Restliste xs
alle diejenigen auszuwählen, die größer als x
sind, und alle jene, die es nicht sind.
Wie man es von Quicksort erwartet, besitzt auch diese Implementierung eine mittlere asymptotische Laufzeit von O(n·logn) und eine Worst-Case-Laufzeit von O(n²). Im Gegensatz zur geläufigen Implementierung in einer imperativen Sprache arbeitet dieses qsort
jedoch nicht in-place.
Algebra Bearbeiten
Dieses Beispiel stellt die Nutzung von Typklassen heraus.
data PhiNum a = PhiNum { numPart :: a, phiPart :: a } deriving (Eq, Show) instance Num a => Num (PhiNum a) where fromInteger n = PhiNum (fromInteger n) 0 PhiNum a b + PhiNum c d = PhiNum (a+c) (b+d) PhiNum a b * PhiNum c d = PhiNum (a*c+b*d) (a*d+b*c+b*d) negate (PhiNum a b) = PhiNum (-a) (-b) abs = undefined signum = undefined fib n = phiPart $ PhiNum 0 1 ^ n
fib
stellt eine schnelle Berechnung von Elementen der Fibonacci-Folge dar. Ausgenutzt wird das vordefinierte ^
, das auf Num
-implementierenden Typen arbeitet.
Implementierungen Bearbeiten
Es gibt inzwischen eine Reihe Haskell-Implementierungen, von denen die meisten aber den Sprachstandard nicht vollständig umsetzen.
- Der Glasgow Haskell Compiler (GHC) unterstützt Haskell 98 sowie zahlreiche Spracherweiterungen. Er übersetzt Haskell-Programme in Maschinencode; für nicht direkt unterstützte Plattformen erzeugt er C-Code, der dann mit einem C-Compiler übersetzt wird.
- Hugs ist ein Bytecode-Compiler, der Haskell 98 fast vollständig sowie einige Erweiterungen implementiert. Hugs ist selbst in C geschrieben.
- nhc (auch nhc98) ist ein weiterer Bytecode-Compiler, der Haskell 98 mit gewissen Einschränkungen unterstützt. Der York Haskell Compiler oder Yhc ist eine Weiterentwicklung von nhc mit dem Ziel, Portabilität und Performance der kompilierten Programme zu verbessern.
- Der Utrecht Haskell Compiler (UHC) ist eine experimentelle Implementierung, die an der Universität Utrecht entwickelt wird. Der Compiler basiert auf Attributgrammatiken und übersetzt Haskell in C-Code. Er implementiert Haskell 98 fast vollständig sowie einige Erweiterungen.
- Helium wird ebenfalls an der Universität Utrecht entwickelt. Der Schwerpunkt des Projekts liegt darauf, leicht verständliche Fehlermeldungen zu erzeugen, um Anfängern das Erlernen von Haskell zu erleichtern. Daher wird auch ein eingeschränkter Haskell-Dialekt implementiert, der unter anderem keine Typklassen hat.
Die hier genannten Implementierungen sind alle Open-Source-Software. Bis auf Hugs sind sie auch alle in Haskell selbst implementiert.
Einfluss Bearbeiten
Haskell dient wegen seiner stark akademischen Herkunft vielen Programmier- und Scriptsprachen als Vorbild für neue Sprachfunktionalität. So haben u. a. Perl, Python, JavaScript, Java, Scala, Rust und PHP Ideen der funktionalen Programmierung von Haskell übernommen. Dazu gehören Funktionen höherer Ordnung wie map, filter usw., Teile der Art, wie generische Programmierung implementiert wurde, und anderes.
Siehe auch Bearbeiten
- International Conference on Functional Programming Contest.
- Pugs (eine Perl-6-Implementierung in Haskell).
- DAML, eine smart contract Sprache basierend auf Glasgow Haskell Compiler.
Literatur Bearbeiten
- Richard Bird: Introduction to Functional Programming using Haskell. 2. Auflage. Prentice Hall Europe, 1998, ISBN 0-13-484346-0 (englisch).
- Marco Block, Adrian Neumann: Haskell-Intensivkurs: Ein kompakter Einstieg in die funktionale Programmierung. Springer, Heidelberg u. a. 2011, ISBN 978-3-642-04717-6, doi:10.1007/978-3-642-04718-3.
- Paul Hudak: The Haskell school of expression: Learning functional programming through multimedia. Cambridge University Press, Cambridge u. a. 2000, ISBN 0-521-64338-4 (englisch, Neuauflage: The Haskell school of music (PDF; 2,4 MB), Version 2.2, 2012).
- Ernst-Erich Doberkat: Haskell – Eine Einführung für Objektorientierte. Oldenbourg Wissenschaftsverlag, München 2012, ISBN 978-3-486-71417-3.
- John Hughes: Why functional programming matters. In: The Computer Journal. Band 32, Nr. 2, 1989, S. 98–107 (englisch, chalmers.se [abgerufen am 18. April 2017] Vorteile funktionaler Programmierung. Zeigt Formen der Modularisierung, die wesentlich auf Funktionen höherer Ordnung und Bedarfsauswertung beruhen.).
- Miran Lipovača: Learn you a Haskell for great good! A beginner’s guide. No Starch Press, San Francisco 2011, ISBN 1-59327-283-9 (englisch, HTML-Fassung [abgerufen am 18. April 2017]).
- Bryan O’Sullivan, Don Stewart, John Goerzen: Real world Haskell. O’Reilly, Sebastopol 2008, ISBN 0-596-51498-0 (englisch, HTML-Fassung [abgerufen am 18. April 2017]).
- Simon Peyton Jones (Hrsg.): Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003, ISBN 0-521-82614-4 (englisch, haskell.org).
- Simon Thompson: Haskell: The craft of functional programming. 3. Auflage. Addison-Wesley, Harlow / New York 2011, ISBN 978-0-201-88295-7 (englisch).
Weblinks Bearbeiten
- haskell.org – zentrale Anlaufstelle zu der Programmiersprache Haskell mit Hinweisen zum Erlernen von Haskell
- interaktiver online Interpreter mit Tutorial (englisch)
Einzelnachweise Bearbeiten
- (Memento vom 7. Juni 2011 im Internet Archive) an der Yale University
- [Haskell] Announcing Haskell 2010. 24. November 2009 (abgerufen am 11. Januar 2023).
- The Haskell 98 Report: Introduction. Abgerufen am 31. März 2021.
- Bryan O’Sullivan, John Goerzen, Donald Bruce Stewart: Real World Haskell: Code You Can Believe In. "O’Reilly Media, Inc.", 2008, ISBN 978-0-596-55430-9, S. xxx (Vorwort).
- Haskell: Die funktionale Programmiersprache im Portrait. 28. Juli 2020, abgerufen am 30. Juni 2022.
- Jens Ohlig, Hannes Mehnert, Stefanie Schirmer: Das Curry-Buch: Funktional programmieren lernen mit JavaScript. O’Reilly Germany, 2013, ISBN 978-3-86899-370-7, S. 144.
- Peter Pepper: Funktionale Programmierung in OPAL, ML, HASKELL und GOFER. Springer Verlag, 1999, ISBN 978-3-642-98002-2, S. 106.
- Wolfram-Manfred Lippe: Funktionale und Applikative Programmierung: Grundlagen, Sprachen, Implementierungstechniken. Springer-Verlag, 2009, ISBN 978-3-540-89108-6, S. 209.
- haskell.org
- The Glasgow Haskell Compiler. Projekt-Website. Abgerufen am 9. Januar 2010.
- Hugs 98. Projekt-Website. Abgerufen am 9. Januar 2010.
- nhc98. Projekt-Website. Abgerufen am 9. Januar 2010.
- Niklas Rojemo: nhc – Nearly a Haskell Compiler. (PDF) Chalmers Tech Report, 1994.
- Atze Dijkstra, Jeroen Fokker, S. Doaitse Swierstra: The architecture of the Utrecht Haskell compiler. In: Haskell ’09: Proceedings of the 2nd ACM SIGPLAN symposium on Haskell. ACM, New York NY 2009, S. 93–104, doi:10.1145/1596638.1596650.
- Bastiaan Heeren, Daan Leijen, Arjan van IJzendoorn: Helium, for learning Haskell. In: Haskell ’03: Proceedings of the 2003 ACM SIGPLAN workshop on Haskell. ACM, New York NY 2003, S. 62–71, doi:10.1145/871895.871902.