Warum funktionale Programmierung [HASKELL]

[warfley]

Hey ho Leute,
Vorab einmal, dies ist kein Tutorial, ich werde hier niemandem Haskell beibringen. Ich erstelle diesen Thread um euch die funktionale Programmierung vorzustellen und warum es sich lohnt funktionale Sprachen zu lernen. Ich werde euch hier einige Features funktionaler Sprachen erläutern, die die Funktionale Programmierung so einfach und effizient gestalten. Dies werde ich an Beispielen in der Sprache Haskell erläutern. Für jeden der Haskell lernen will werde ich am Ende ein paar Tutorials oder Bücher auflisten.

Einleitung

Was ist funktionales programmieren?

Die meisten Leute, die mit dem Programmieren anfangen, lernen so genannte imperative Programmiersprachen wie C#, Java, C++ oder ähnliches. Imperative Sprachen verwirklichen das Konzept durch eine Reihe von anweisungen dem Computer zu sagen was er tuen soll, und der Computer führt diesen Code dann Schritt für Schritt aus. Man definiert also wie etwas gemacht wird.

Dem gegenüber stehen die deklarativen Sprachen, zu denen auch die funktionalen Sprachen gehören. In deklarativen Sprachen wird durch Definitionen festgelegt was getan werden soll, und der Compiler entscheidet dann wie es umgesetzt wird.

Die funktionalen Sprachen bauen vollständig auf der Nutzung von Funktionen auf, wobei sich diese deutlich von den Funktionen aus der imperativen Programmierung unterscheiden. Zunächsteinmal die wohl wichtigste Eigenschaft ist, es gibt keine inneren Zustände. Das heißt die Funktionen stehen in keinem Kontext mit anderen Daten, Funktionen sind also frei von Seiteneffekten. Während z.B. in Java jede Methode zu einem Objekt gehört, welches Eigenschaften hat welche die Funktion beeinflussen können, ist dies in der funktionalen Programmierung nicht der Fall. Ein Funktionsaufruf mit dem selben Argument gibt immer das selbe Ergebnis.
Eine andere wichtige Eigenschaft ist, Funktionen sind reguläre Datenobjekte wie Integer oder Doubles, können über Operationen modifiziert werden.

Warum sollte ich Funktionale Programmierung lernen?

Nun es gibt viele Gründe, falls ihr bereits imperatives Programmieren gelernt habt, und von funktionaler Programmierung noch nichts wisst, dann lohnt es sich allein schon um neue Konzepte kennen zu lernen, um bei eurem nächsten Projekt die Optimale Sprache für eure Anforderungen zu wählen.

Aufgrund seiner sehr einfachen und wartbaren Eigenschafften wird Haskell oft in gebieten verwendet in denen schnell Algorithmen entwickelt werden müssen, und deren Korrektheit im Vordergrund steht. So z.B. bei Netzwerkprotokollen, so verwenden riesige Konzerne AT&T oder Ericsson Funktionale Sprachen zur entwicklung der Algorithmen, da sie damit schnell auftretende Probleme beheben können, und dabei keine Fehler aufgrund falscher Implementierung oder Seiteneffekten auftreten. Erricson berichtet sogar davon das seit dem Umstieg auf Funktionale Programmierung (mit Erlang) Zeiteinsparungen von einem Faktor 2 bis 10 gemessen haben.

Für neueinsteiger lohnt sich Haskell vor allem durch seine Einfachheit. Durch das wegfallen der Seitenefekte, und die deklarative Natur, muss man sich kaum gedanken über mögliche Fehlerquellen machen, sondern kann Zielgerichtet drauf los programmieren.

Warum Haskell?

Es gibt viele Funktionale Sprachen, der grund warum ich mich für Haskell entschieden habe ist ziemlich simpel, ich musste Haskell für die Uni lernen, und daher kann ich Haskell einfach am besten. Allerdings gibt es noch einige, nicht so subjektive Gründe für Haskell.

1. Haskell ist nur Funktional. Im gegensatz zu OCaml welches auch OO Eigenschafften hat, kann man sich bei dem lernen von Haskell rein auf die funktionalen Eigenschaften konzentrieren.
2. Open Source. Der GHC (Glasgow Haskell Compiler) als der wichtigste Haskell Compiler ist Open Source, und durch die sehr aktive Community gibt es auch viele Open Source packages.
3. Einfache Syntax. Die Haskell Syntax ist klar strukturiert und dennoch einfach zu lesen.
4. Schnell. Der GHC erzeugt meist sehr effizienten und schnellen Code, dessen Performance sich nicht verstecken muss.
5. Interpreter. Neben dem Compiler gibt es noch den GHCi, einen Interpreter, mit dem man code schnell testen kann.

Weitere Informationen zu Haskell findet ihr auf der Haskell Website:

Funktionale Programmierung

Zunächst einmal sollte man alles Vergessen was man aus der Imperativen Programmierung kennt, funktionale Programmierung geht anders, es ist eine komplett andere Welt mit einer Komplett anderen Herangehensweise.

Die Ausführung eines Haskell Programms besteht aus der der Auswertung von Ausdrücken. So ist 2 + 3 ein gültiger Ausdruck und würde von Haskell zu 5 ausgewertet werden. Bei der Auswertung solcher Ausdrücke greift der Compiler auf die Deklarationen zurück die ihm gegeben wird. in diesem Beispiel wird der Infixoperator (+) verwendet, welcher von Haskell vordefiniert ist.
Um also kompliziertere Ausdrücke zu konstruieren müssen wir wissen wie wir selbst dinge deklarieren.

Beginnen wir zunächst einmal mit den Funktionsdeklarationen, es gibt ein und Nullstellige Funktionen. Nullstellige Funktionen sind dabei Konstanten.
Die Syntax orientiert sich hierbei an der Mathematik. So würde die Mathematische Notation

drei ∈ ℤ
drei = 3

Die Haskell notation

drei :: Int
drei = 3

Somit hätten wir eine Konstante drei mit dem Wert 3 definiert. Die obere Zeile gibt die Signatur der Deklaration an, in unserem Fall ist es also eine Konstante vom Typ Integer.

Einstellige Funktionen, also funktionen die einen Eingabewert erhalten und einen Ausgabewert liefern lassen sich auch sehr ähnlich der mathematischen Syntax definieren.

Die dbl funktion welche das Argument verdoppelt sieht mathematisch so aus

doppel: ℤ -> ℤ
doppel(x) = x + x

Lässt sich in Haskell so realisieren

doppel :: Int -> Int
doppel x = x + x

Was auffällt, Haskell hat keine Klammern um die Argumente. Dies ist nicht nur bei der Deklaration sondern auch beim Aufruf so. Haskell würde den Ausdruck doppel 2 also zu 4 auswerten. Man könnte zwar auch doppel(x) = x+x schreiben oder den Ausdruck doppel(2) aufschreiben, aber solange es nicht zu verwirrungen kommt, braucht man keine zusätzlichen klammern.


Wie ich bereits gesagt habe können Funktionen nur Ein- oder Nullstellig sein, um nun Funktionen zu realisieren welche Mehrstellig sind, also mehr als nur ein Argument entgegen nehmen bietet Haskell die Möglichkeit Kathesische Produkte zu verwenden, so wie es auch in der Mathematik der Fall ist. Als Argument wird dann ein Tupel mit verschiedenen Objekten verwendet statt nur einem Objekt.

Betrachten wir diese sehr einfache Funktion in mathematischer Notation

plus: ℤxℤ -> ℤ
plus(x, y) = x + y

Diese nimmt als Tupel 2 ganze Zahlen. In Haskell würde das so aussehen

plus :: (Int, Int) -> Int
plus (x, y) = x + y

Nun das ist allerdings recht aufwendig, immer die Klammern zu tippen, daher gibt es noch eine andere Möglichkeit zweistellige Funktionen zu Realisieren, undzwar

plus :: Int -> Int -> Int
plus x y = x + y

Jede Funktion lässt sich von der Tupelschreibweise zur nicht Tupel Schreibweise umformen, dieser Prozess heißt Curry (nach dem Haskell Erfinder benannt).

Obwohl es in Haskell keine mehrstelligen Funktionen gibt ist dieser Vorgang dennoch möglich, durch eine Eigenschaft auf die ich später zurück kommen will, den Funktionen Höherer Ordnung. Hier ist nur wichtig das man mehrstellige Funktionen genau wie Einstellige Funktionen über den Funktionsoperator deklarieren kann.


In der funktionalen Programmierung mit Haskell sind Listen ein wichtiges Kernstück. Listen werden mit der Signatur [Typ] angegeben, z.B. [Int] ist eine Liste von Integer Objekten.

Listen sind (wie sogut wie alles in Haskell) rekursiv definiert. Es gibt die Leere Liste [], sowie den infix Operator : mit dem ein Element zur Liste Hinzugefügt werden kann. x : xs bezeichnet dabei die Liste mit dem ersten Element x, gefolgt von den Elementen der Liste xs. Die Liste [3, 5, 4, 10] ist also ledeglich der Ausdruck 3 : (5 : (4 : (10 : []))). Allerdings aufgrund der kürzeren un übersichtlicheren Schreibweise, verwendet man normalerweise die [Werte] Syntax.

Pattern matching

Betrachten wir die plus Funktion von oben nocheinmal genauer

plus x y = x + y

hier findet das so genannte pattern matching statt. Hinter plus und vor dem = steht das Muster (engl. pattern) für die Argumente. Wir bekommen zwei Argumente (wie in der Signatur angegeben) rein. Das Pattern bestimmt nun, wie diese Argumente auszusehen haben, und nur wenn die Argumente zu diesem Muster passen, wird der Ausdruck hinter dem = Symbol zurückgegeben.

Das Muster kann aus verschiedenen dingen bestehen, aus Konstanten (Zahlen, oder Bezeichnern mit die Großbuchstaben anfangen), aus Variablen (Bezeichner die mit Kleinbuchstaben anfangen), Wildcard _ und natürlich kompositionen aus diesen.

Bei dem Einsatz von Variablen wird versucht die Eingabe durch diese Variablen zu substituieren. Unsere Funktion bekommt zwei Integer Objekte, Haskell erkennt nun das Muster enthält zwei Variablen, also wird das erste Argument mit x substituiert und das zweite mit y. Wenn man nun x oder y auf der rechten Seite des = verwendet, so weiß Haskell das damit diese Argumente bezeichnet werden.

Durch die verwendung von Konstanten kann überprüft werden ob das Argument den korrekten Wert hat. Nehmen wir diese einfache Funktion (Hinweis: Bool ist ein Wahrheitstyp und kann die Werte Wahr(True) oder Falsch(False) annehmen)

istDrei :: Int -> Bool
istDrei 3 = True

Dies bedeutet, Haskell fürt die zweite Zeile nur dann aus, wenn das eingegebene Argument auch wirklich 3 ist.

Wenn man nun istDrei 4 aufrufen würde, würde es zu einem Fehler kommen, da Haskell das Argument 4 nicht umschreiben kann, sodass daraus 3 wird. Um nun auch andere Fälle abzudecken, kann man verschiedene Muster angeben.

istDrei :: Int -> Bool
istDrei 3 = True
istDrei _ = False

Nun würde Haskell bei dem Ausdruck istDrei 4 zunächst die erste Definition überprüfen, sehe dass dieses Muster nicht auf das Argument 4 anzuwenden ist, und das nächste Muster überprüfen. Wildcard steht für jede mögliche Eingabe, daher erkennt Haskell das 4 durch Wildcard ausdrücken kann, und wählt das Ergebnis False.

Patterns können auch komplizierter sein, so kann man z.B. Listen auf die Rekursive : notation überprüfen. Betrachten wir die folgende Funktion

headIntList :: [Int] -> Int
headIntList (x:xs) = x

Wie oben erwähnt bezeichnet x:xs die Liste xs wenn man x als erstes element dran hängt. Bei dem Ausdruck headIntList [3, 5, 6] würde Haskell nun erkennen das es sich um den Ausdruck headIntList 3 : (5 : (6 : [])) handelt, und hier lässt sich nun 3 zu x und (5 : (6 : [])) zu xs substituieren, und somit ist x : xs = 3 : (5 : (6 : [])) = [3, 5, 6]. Nun kann man auf der rechten Seite des = x für das erste Element und xs für die Restliste verwenden.


Das Pattern matching ist ein sehr mächtiges Tool, da man damit die Argumente direkt verarbeiten kann, so wie in dem headIntList Beispiel schon durch das Pattern das erste Element separiert wurde, und gleichzeitig die restliste Berechnet wurde. Zum anderen kann man damit unterscheiden was die Funktion zurückgeben soll, abhängig von der Eingabe. Hier ein weiteres Beispiel

example :: [Int] -> Int
example [] = 0
example x : [] = 3
example _:x:xs = x

Diese Funktion gibt bei der Übergabe einer leeren Liste 0 zurück, wenn die Liste nur ein Element hat, gibt sie dieses zurück, ansonsten das zweite Element der Liste.


Bedingungen

Durch die deklarative Natur Haskells, verwendet man keine aus der imperativen Programmierung bekannten Kontrollstrukturen wie if Abfragen oder Schleifen. If Abfragen können z.B. mit dem Pattern matching gelöst werden. Eine weitere möglichkeit Abfragen durchzuführen ist die Bedingte definition. Betrachten wir folgende Funktion der Mathematik

maxNum: ℤxℤ -> ℤ
maxNum(x, y) = 	x falls x >= y
			y sonst

Diese Form der Bedingung gibt es auch so in Haskell

maxNum :: Int -> Int -> Int
maxNum x y 	| x >= y		= x
		| otherwise 	= y

Dies lässt sich auch einzeilig umschreiben in

maxNum x y = if x >= < then x else y

Hinweis: Wenn in Haskell eine neue Zeile weiter eingerückt beginnt als die vorherige, dann gehört diese Zeile zu der vorherigen

Lokale Deklarationen

Neben den Globalen deklarationen können auch lokale, funktionsinterne deklarationen konstruiert werden. Dafür gibt es das Schlüsselwort where, auf das dann verschiedene Deklarationen folgen können

doppel :: Int -> Int
doppel x = y
	where y = x + x

Hier wird y definiert als x+x. Damit lassen sich Funktionsdefinitionen verkürzen durch entfernen von redundanzen, und die leserlichkeit erhöht sich.


Rekursion

In der funktionalen Programmierung gibt es keine Schleifen, daher ist Rekursion ein sehr wichtiges Konzept. Wollen wir eine Funtion konstruieren welche uns die Länge einer Liste zurückgibt können wir dies ohne Schleifen nur mit Rekursion und Pattern matching lösen

lenIntList :: [Int] -> Int
lenIntList [] = 0
lenIntList x:xs = 1 + len xs

Diese funktion basiert auf dem Basisfall, das bekannt ist, eine leere Liste hat 0 elemente. Ist die Liste nicht leer, so enthält sie mindestens Element, also ist die größe um eins größer als die der Restliste. Der ausdruck len [1, 2] wird damit wie folgt ausgewertet

len [1, 2] = 1 + len [2] = 1 + 1 + len [] = 1 + 1 + 0 = 2

Rekursion kommt allerdings nicht nur in Funktionsdeklarationen zum Einsatz, sondern auch in Datenobjekten. Wie oben bereits erwähnt sind Listen in Haskell auch rekursiv definiert. Eine Liste ist definiert als entweder die leere Liste [] oder eine konstruktion x:xs mit x einem Wert und xs einer anderen Liste (z.B. []).

Neben den vordefinierten Listen ist es allerdings auch möglich selbst Rekursive Typen zu definieren. Die definition eines Binären Integer Baums sieht z.B. so aus

data BinTree = 	Leaf Int
		| Fork (BinTree) (BinTree)

Dies definiert einen BinTree als entweder ein Leaf mit einem Integer Wert, oder einem Fork in zwei neue BinTree. Leaf und Fork heißen hierbei nun Konstruktoren, da diese die Datenobjekte Konstruieren. Leaf 3 ist somit der Baum der nur das Element 3 enthält. Fork (Leaf 3) (Leaf 4) wiederum konstruiert einen Baum mit einer Verzweigung und an dessen Ende sind die Blätter mit Wert 3 und 4. Somit lassen sich beliebig große Binäre Bäume bauen.

Betrachten wir eine Funktion die mit einem solchen Baum arbeitet

sumTree :: BinTree -> Int
sumTree (Leaf x) = x
sumTree (Fork x y) = sumTree x + sumTree y

Der Ausdruck sumTree (Fork (Fork (Leaf 2) (Leaf 3)) (Leaf 1)) würde somit also zu 6 ausgewertet werden.

Higher-Order Funktionen

Ich habe bereits erklärt, es gibt in Haskell keine Mehrstelligen Funktionen, aber mit dem Currying ist es dennoch möglich Mehrstellige Funktionen zu definieren. Um dies zu verstehen betrachten wir doch mal unsere gecurryte plus Funktion:

plus :: Int -> Int -> Int

Der -> Operator assoziiert nach rechts, somit ergibt sicht mit der Implizieten Klammerung

plus :: Int -> (Int -> Int)

Was man nun hier sieht ist, die Funktion ist tatsächlich einstellig, und nimmt einen Integer als Argument, und gibt eine Funktion zurück.
Dies ist möglich da Funktionen reguläre Objekte sind. Der Ausdruck plus 2 3 wird also ausgewertet zu (plus 1) 2, wobei plus 1 uns eine Funktion zurückgibt die auf den Eingabewert eins addiert.

Wir können uns damit weitere Funktionen auch definieren

nachfolger :: Int -> Int
nachfolger = plus 1

Wenn eine Funktion andere Funktionen als Argument bzw. Ergebnis verwendet, so bezeichnet man diese als Higher-Order Funktion.
Diese bieten vor allem generische Vorlagen zum konstruieren neuer Funktionen, so wie wir die Funktion nachfolger mithilfe von plus konstruiert haben.

Eine der wohl wichtigsten Funktionen höherer Ordnung ist die map funktion. Diese nimmt eine Funktion und eine Liste entgegen und gibt eine Liste zurück mit den Elementen der Eingabe liste auf die die Funktion angewendet wurde. Wenn man nun map nur eine Funktion übergibt so erhalten wir eine neue Listenmodulierungsfunktion

incList :: [Int] -> Int
incList = map nachfolger

incList [1, 2, 3] wird somit zu [2, 3, 4] ausgewertet.

Polymorphes Typsystem

Haskell bietet ein Polymorphes Typsystem, das ist ungefähr patternmatching mit Typen. Man kann in Funktionssignaturen Variablen für Typen angeben, und dann kann die Funktion für beliebige Typen angewendet werden.

id :: a -> a
id x = x

Diese Funktion nimmt ein Argument beliebigen Typs entgegen, und gibt es wieder Zurück. Kentniss über den Typen braucht man dabei nicht.

Betrachten wir unsere len Funktion zur berechnung der Länge einer Liste. Diese lässt sich auch Typneutral umformen

len :: [a] -> Int
len [] = 0
len x:xs = 1 + len xs

Somit lässt sich diese Funktion auf jeden beliebigen Listentypen anwenden.
Wenn man in der Signatur die Typvariable doppelt verwendet, so müssen diese beiden den Selben typ haben, bei id :: a -> a bedeutet das, das die Eingabe und Ausgabe den selben Typen haben müssen, welcher ist aber egal.
Die Signatur von map ist z.B.

map :: (a -> b) -> [a] -> [b]

Listenkomprehensionen

Wer sich schonmal mit Mathematik beschäfftigt hat kennt diese Notation

{ f(x) | x ∈ [1, 10], Bedingungen(x)}

Dies definiert die Menge der Funktionswerte f(x) aller Zahlen x aus der menge ℤ welche die Bedingungen Bedingungen(x) erfüllen.
Haskell unterstützt diese notation für Listen

[f x | x <- [1..10], bedingungen]

Somit lässt sich sehr viel Zeit sparen. z.B. den Quicksort algorithmus in Haskell (++ Verknüpft zwei listen)

qSort :: [Int] -> [Int]
qSort [] = []
qsort (x:xs) = qSort lesser ++ [x] ++ qsort bigger
	where 	lesser = [y | y<-xs, y <=x]
		bigger = [y | y<-xs, y > x]

Nun wer schon einmal einen Quicksort in Java oder C++ gesehen hat weiß, der wird niemals so einfach aussehen


Unendliche Datenobjekte

Haskell unterstützt unendliche Objekte. Z.B. Eine Liste welche ohne die leere Liste als Ende Konstruiert wird, sondern mit unendlich vielen Zahlen

inflist = 1 : inflist

Diese nullstellige Funktion ist rekursiv endlos definiert. Etwas was bei Java direkt zu einem Stack Overflow mit entsprechender Exception führen würde, kann in Haskell problemlos verwendet werden. Wenn man in den ghci nun inflist eintippen würde, so würde er nie terminieren, aber durchgehend neue einsen ausspucken.

Dies funktioniert durch Haskells Lazy Evaluation Auswertungsstrategie. Diese hier ausführlich zu erklären würde viel zu viel Platz und Zeit brauchen, die Idee ist allerdings einfach, Haskell generiert die Liste nur so weit wie es nötig ist.

Um das zu illustrieren betrachten wir die Funktion take

take :: Int -> [a] -> [a]
take 0 _ = []
take y (x:xs) = x : take (y-1) xs

Diese nimmt eine Zahl y und eine Liste als Argument, und gibt dann die ersten y Elemente der Liste zurück. Ruft man nun take 3 inflist auf, sowertet Haskell den ausdruck wie folgt aus:

take 2 inflist =(1) take 2 1:inflist =(2) 1 : (take 1 inflist) =(3) 1 : (take 1 1:inflist) =(4) 1 : (1 : (take 0 inflist)) =(5) 1 : (1 : [])

in (1) und (3) wird inflist einen Schritt weit aufgelöst, damit mit dem Pattern matching angefangen werden kann. In (2) und (4) erkennt Haskell bereits ein Pattern, muss also inflist nicht weiter auflösen um die Teillösung zu berechnen. In 5 erkennt Haskell dann das Basisfall pattern, welches es unabhängig von der Liste inflist terminieren lässt.


Schlusswort

So das war mein kleiner Einblick in die Welt von Haskell, und seine unikaten Features. Ich hoffe ich habe einigen eventuell lust auf mehr gemacht.
Falls ihr daran interresiert seit Haskell richtig zu lernen kann ich das Skript meines Professors empfehlen
Oder das Buch: Thinking Functionally With Haskell von Richard Bird (Professor der Oxford University) ISBN: 9781107452640