Loading AI tools
funktionale Programmiersprache Aus Wikipedia, der freien Enzyklopädie
Haskell ist eine rein funktionale Programmiersprache[3], 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,[1] Philip Wadler et al. |
Aktuelle Version | Haskell 2010[2] (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 |
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 nicht daran interessiert. So wurde 1990 Haskell 1.0 veröffentlicht.[4]
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.[5]
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 vom Kontext, in dem die Funktion aufgerufen wird (z. B. Zeitpunkt des Aufrufs). Daraus folgt, dass bei wiederholtem Aufrufen einer Funktion mit denselben Parametern auch jedes Mal dasselbe Ergebnis folgt. Dies können Haskell-Implementationen nutzen, um Funktionen zu cachen.
Es gibt keine nativen imperativen Sprachkonstrukte. Durch die IO-Monade ist es möglich, Ein- und Ausgabeoperationen und zustandsabhängige Berechnungen, wie Zufallszahlengeneratoren, rein funktional zu behandeln. Haskell stellt jedoch die sogenannte do-Notation bereit, welche es erlaubt, die Verkettung von Monaden in Stil von imperativen Sprachen darzustellen
-- Die Definition einer IO aktion, welche einen Namen von der Konsole einliest
-- und dann den String "Hallo <name>! Willkommen" ausgibt
aktion = getLine >>= (\eingabe -> putStr ("Hallo, " ++ eingabe)) >> putStrLn "! Willkommen"
-- Eine Identische Definition mit do-Notation
aktion = do
eingabe <- getLine
putStr ("Hallo, " ++ eingabe)
putStrLn "! Willkommen"
Es gibt keine Unterscheidung zwischen Variablen und Konstanten, da der Wert einer Variable in Haskell nicht verändert werden kann. Man spricht von unveränderlichen oder nicht veränderbaren Variablen. Dies ist auch der Grund, weshalb es keine Unterscheidung von Identität und Gleichwertigkeit von Variablen gibt. Durch diese Eigenschaften ist Haskell der Mathematik sehr nahe und es ist möglich, die Richtigkeit gewisser Programme zu beweisen, beispielsweise durch Vollständige Induktion.
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
first
liefert bei Eingabe zweier Parameter den ersten als Ergebnis zurück. Bei der Eingabe von first x (3+7)
ist die Auswertung der Summe (3+7)
zur Ergebnisbestimmung nicht notwendig, sollte also unberücksichtigt bleiben.quadrat
berechnet bei Eingabe eines Parameters dessen Quadrat. Bei Eingabe von quadrat(3+5)
, was im Laufe des Auswertungsprozesses zu (3+5)*(3+5)
wird, wäre eine doppelte Berechnung der Summe (3+5)
ineffizient, sollte also vermieden werden.map
wendet eine beliebige Funktion auf die Elemente einer Liste an. Ihr Typ wird so angegeben: map :: (a -> b) -> [a] -> [b]
map
etwa mit der speziellen Funktion toUpper
vom Typ Char -> Char
aufgerufen, ergibt der Typabgleich map toUpper :: [Char] -> [Char]
map
-Funktion, die eine Funktion f
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]
(a, b) -> c
verwendet, ist in Haskell die Curry-Form a -> b -> c
üblicher. Damit wird die partielle Auswertung von Funktionen bequem möglich. Der Ausdruck map toUpper
ist beispielsweise eine teilweise Auswertung von map
, denn er beschreibt eine Funktion, nämlich die Funktion, welche alle Kleinbuchstaben einer Liste in Großbuchstaben verwandelt. data Tree = Leaf Int | Branch Int Tree Tree
Tree
besteht entweder aus einem Blatt (Leaf Int
) oder einer Verzweigung (Branch Int t1 t2
), wobei t1
und t2
die Teilbäume darstellen, die wiederum die Struktur Tree
haben. Zur Definition dieser Datenstruktur wurde sowohl der einstellige Konstruktor Leaf
als auch der dreistellige Konstruktor Branch
verwendet. data Tag = Montag | Dienstag | Mittwoch | Donnerstag | Freitag | Samstag | Sonntag
deriving (Show, Eq, Ord, Ix, Enum)
Char
und freien Typvariablen auch noch Typvariablen mit Einschränkung auf bestimmte Klassen verwendet werden.==
-Methode der Klasse Eq
der Vergleich sowohl zweier Zahlen als auch zweier Texte möglich. Trotzdem arbeitet der Gleichheitstest je nach Argumenttyp anders.IO
. putStrLn :: String -> IO ()
getLine :: IO String
putStrLn
gibt einen Text und einen Zeilenumbruch auf der Standardausgabe aus. Da es kein informationstragendes Ergebnis gibt, wird der Einheitstyp ()
als Rückgabetyp verwendet. getLine
liest eine Textzeile von der Standardeingabe. Der IO
-Typkonstruktor stellt sicher, dass man den Nutzern der Funktion offenlegen muss, dass die Ergebnisse durch Ein-/Ausgabe gewonnen wurden. Diese strenge Handhabung ermuntert Haskell-Programmierer zur klaren Trennung von Ein- und Ausgabe und anderen Teilen eines Programms. Der größte Teil eines Haskell-Programms besteht in der Regel aus Funktionen ohne Ein- und Ausgabe. Man kann IO
-Typen natürlich auch in andere Typen einbetten und so zum Beispiel einen speziellen IO-Typ definieren, der nur Eingaben erlaubt.Haskell unterscheidet Groß- und Kleinschreibung.[8] 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.
do
-Notation verleiht Berechnungen mit Monaden das Aussehen von imperativen Programmen. readFile "eingabe.txt" >>= writeFile "ausgabe.txt"
readFile "eingabe.txt" >>= (\inhalt -> writeFile "ausgabe.txt" inhalt)
do inhalt <- readFile "eingabe.txt"
writeFile "ausgabe.txt" inhalt
a + b = (+) a b
a `div` b = div a b
..
) 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
pat <- xs
), Prädikaten (Ausdrücken mit dem Typ Bool
) und let
-Bindungen angegeben werden. Insbesondere ist es möglich, überhaupt keine Generatoren zu verwenden. Der Ausdruck [x | odd x]
x
, welches als bereits definiert vorausgesetzt wird, den Wert []
oder [x]
an. fak :: Integer -> Integer
fak 0 = 1
fak n = n * fak (n-1)
fak
berechnet die Fakultät einer Zahl. 0
und n
sind dabei die Muster (Pattern), von denen die Ergebnisbestimmung abhängt. Für Zahlen größer als 0 greift nur das Muster n
, so dass zweitere Alternative verwendet wird. Diese errechnet das Ergebnis durch n * fak (n-1)
, wobei sie sich, solange (n-1) > 0
ist, rekursiv selbst aufruft, bis sie bei 0
ankommt. Dort greift dann das Muster 0
, so dass erstere Alternative verwendet wird, welches die Rekursion sauber abschließt, 1
zurückgibt und die Rücksprungkette einleitet.Zu Haskell gehört auch ein Modulsystem. Der Haskell-98-Standard definiert eine Grundmenge von Modulen,[9] 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,
import Data.List(delete)
x = delete 'a' "abc"
import qualified Data.List
x = Data.List.delete 'a' "abc"
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
.
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
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)))
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.
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.
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.
Es gibt inzwischen eine Reihe Haskell-Implementierungen, von denen die meisten aber den Sprachstandard nicht vollständig umsetzen.
Die hier genannten Implementierungen sind alle Open-Source-Software. Bis auf Hugs sind sie auch alle in Haskell selbst implementiert.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.