Haskell Tutorial

Zusammenfassung des Projekts

Zielgruppe:

Lernziele:

Buchpatenschaft/Ansprechperson: Dirk Huenniger

Sind Co-Autoren gegenwärtig erwünscht?

Richtlinien für Co-Autoren:

Projektumfang und Abgrenzung zu anderen Wikibooks:

Themenbeschreibung:

Aufbau des Buches:

Einleitung

Dieses Tutorial erklärt anhand weniger einfacher Beispiele die Programmiersprache Haskell. Zielgruppe sind Menschen im Alter von ca. 12 Jahren bis $\infty$ . Ein bisschen Programmiererfahrung ist von Vorteil, aber auch nicht so wichtig, da Haskell sich so stark von den verbreitesten Sprachen unterscheidet, dass man fast alles neu lernen muss. Mein Ziel ist es, hier möglichst kleinschrittig vorzugehen und auch nicht sehr in die Tiefe zu gehen. Im Haskell-Wiki gibt es wunderschöne Tutorials. Wer diese lesen und verstehen kann, sollte sich besser an diese halten. Wer damit nicht so gut klarkommt, vielleicht auch weil dort fast alles auf English erklärt wird, kann sich mal mit dem hier vorliegenden Text versuchen.

Hello World

main = putStrLn "Hello World"

Diesen Code speichert man in der Datei hello.hs. Zum Kompilieren braucht man den Glasgow Haskel Compiler (GHC). Den ruft man so auf:

ghc --make hello.hs

Dann führt man Programm aus (hier für Linux beschrieben, sonst auch hello.exe):

./hello

Auf der Ausgabe erscheint nun:

Hello World

So weit so gut. Das Programm wirkt ziemlich trivial. Es ist aber in Wahrheit kompliziert. Beides ist ein Grund, es nicht im Detail zu erklären. Eine Frage stellt sich der erfahrene Programmierer vielleicht und zwar: warum muss es nicht so heißen?

main = putStrLn ("Hello World")

Das geht auch. Und Haskell ist das ziemlich egal. Man kann nur in Haskell sehr viele Zeichen, die man sonst hinschreiben muss, weglassen. Und Programme werden dadurch meist übersichtlicher. "Hello World" steht direkt rechts neben putStrLn. Das reicht Haskell schon um zu wissen, dass "Hello World" ein Parameter ist, der an die Funktion putStrLn übergeben wird.

Also weiter, versuchen wir einmal ein ähnliches Beispiel.

main = putStrLn 42

Aber das kompiliert nicht! Aber das hier kompiliert:

main = putStrLn (show 42)

Hier übergeben wir die Zahl 42 an die Funktion show. Diese erzeugt hierraus einen String und gibt diesen an putStrLn weiter. Das coole an show ist, dass es so ziemlich alles in ziemlich brauchbare strings verwandelt. Auch selbst definiete Datentypen. In anderen Sprachen verwendet man Objekte und Klassen um zu programmieren. In Haskell nimmt man Datentypen und man kann sehr viel damit tun, mindestens so viel wie mit Klassen und Objekten in anderen Sprachen aber halt auf eine völlig andere Art und Weise. Wir schauen uns noch mal ein Beispiel dafür an was show so kann.

Listen

main = putStrLn (show ([1,2]++[3,4]))

Die Ausgabe ist.

[1,2,3,4]

++ ist der Listen Verkettungsoperator (concatenation). Wir fügen also die Listen [1,2] und [3,4] zur Liste [1,2,3,4] zusammen und geben diese aus. Die Ausgabe ist die komplette Liste mit allen Elementen der Liste in einer für Menschen lesbaren Form.

Es gibt ein paar schöne Zaubertricks die man mit Listen veranstalten kann.

main = putStrLn (show   [2*x|x<- [1,2,3,4]])

die Ausgabe ist

[2,4,6,8]

Wir haben also den Wert jedes Listenelements verdoppelt. Wir können natürlich auch quadrieren:

main = putStrLn (show   [ x * x | x <- [1, 2, 3 ,4] ] )

die Ausgabe ist

[1,4,9,16]

Jetzt ist natürlich die Frage wie man diesen Befehl lesen und schreiben muss. Also wir fangen an mit der Liste [1,2,3,4]. Dann gibt es die Zeichenfolge x <-[1, 2, 3, 4] . Ich lese das als. x soll ein Element sein was der Liste [1,2,3,4] entnommen wird. Dann haben wir die Zeichenfolge x*x. Das ist offenbar berechne das Quadrat von x. Und dann noch umschliessende Konstruktion [ x * x | ... ]. Das lese ich als füge das Quadrat von x in die Ausgabeliste ein. Es wird also die 1 der Eingabeliste entnommen. Dann wird sie Quadriert und in die Ausgabeliste eingefügt. Dann die 2, usw. Am Ende wird die Ausgabeliste an show übergeben. show macht daraus einen String und gibt ihn an putStrLn weiter. Und putStrLn gibt ihn auf die Konsole aus.

Listen kann man auch filtern. Das sieht so aus:

main = putStrLn (show   [x|x<- [1,2,3,4], x>2])

Ausgabe ist.

[3,4]

Wir haben also alle x übernommen für die x>2

Aber wir können natürlich auch alle geraden Zahlen nehmen.

main = putStrLn (show   [x|x<- [1,2,3,4], x `mod` 2==0])

Ausgabe ist:

[2,4]

Dabei berechnet `mod` den Rest Division ganzer Zahlen. Wenn eine Zahl mit Rest 0 durch zwei teilbar ist dann (und genau dann) ist sie gerade. Somit bekommen wir hier die geraden Zahlen. Natürlich lassen sich die beiden Zauber auch kombinieren:

main = putStrLn (show   [x*x|x<- [1,2,3,4], x `mod` 2==0])

Ausgabe ist:

[4,16]

Eigene Funktionen

Man kann sich natürlich auch eigene Funktionen definieren.

square = \ x -> x*x
main = putStrLn (show  (square 3))

Ausgabe

Gut, wie ist das zu lesen? square ist eine Funktion und diese bekommt 3 übergeben und gibt das Quadrat von 3 also 9 zurück. Der Aufruf der Funktion square in der zweiten Zeile des Programms ist ganz normal, er geschieht genauso wie der Aufruf von show, oder von putStrLn. Aber dann gibt es noch die erste Zeile in der wir die Funktion square definieren. Es kommt also erst der Name der Funktion, dann ein Gleichheitszeichen, dann ein backslash \ . Dann kommt der Eingabeparameter der Funktion, also in diesem Fall x dann kommt ein Pfeil -> und schließlich die Ausgabe der Funktion in diesem Falle x*x. Es ist also die Funktion die einem Wert x den Wert x*x zuordnet. Diese Schreibweise erinnert etwas an die Schreibweise, in der man in der Schule in Fach Mathematik Funktionen formuliert hat. Natürlich gib es aus Funktionen mit zwei oder noch mehr Parametern. Hier ist so eine.

add = \ x y -> x + y
main = putStrLn (show  (add 10 3))

Ausgabe

Hier stehen die beiden Eingangsparameter x und y zwischen dem backslash \ und dem Pfeil -> und der Ausgabewert der Funktion x+y steht hinter dem Pfeil. Das Verrückte ist nun, dass man Funktionen auch dort definieren kann, wo man sie gerade braucht. Hier noch einmal das Beispiel "Quadrieren", wobei die Funktion in der Ausgabe definiert wird:

main = putStrLn (show  ( (\ x -> x * x) 3))

Ausgabe ist wieder 9. Wir sind ausgegangen von

square = \ x -> x*x
main = putStrLn (show  (square 3))

Danach haben wir das kopiert, was rechts von Gleichheitszeichen bei square steht, also \ x -> x*x . Anschließend haben wir square in der zweiten Zeile durch das Kopierte ersetzt. Wobei wir das Kopierte noch in Klammern gesetzt haben.

square = \ x -> x*x
main = putStrLn (show  ((\ x -> x*x) 3))

Schließlich haben wir noch die Definition von square gelöscht. Also haben wir nur die square durch seine Definition ersetzt. Das ganze wirkt auf den ersten Blick etwas ungewohnt.

Dasselbe funktioniert mit add.

main = putStrLn (show  ((\ x y -> x + y) 10 3))

Auch hier ist die Ausgabe wieder 13.

Mehr über Listen

Die Funktion zum Verarbeiten von Listen, die wir oben gesehen haben, kann man auch noch in einer etwas anderen Art und Weise aufrufen.

main = putStrLn (show  (map (\x -> x*x) [1,2,3,4]))

Ausgabe:

[1,4,9,16]

Und für das Filtern geht das natürlich auch.

main = putStrLn (show  (filter (\x -> x>2) [1,2,3,4]))

Ausgabe:

[3,4]

Es geht sogar noch kürzer.

main = putStrLn (show  (filter (>2) [1,2,3,4]))

führt zum selben Ergebnis. Man kann sich natürlich fragen, was Haskell wohl bei (>2) denkt. Naja es muss heißen (x>2), da x aber fehlt, ist es automatisch eine Funktion die x als Eingabewert entgegennimmt. Das geht nebenbei auch, wenn man zwei oder mehr Parameter weglässt:

main = putStrLn (show ((+) 40 2) )

Ausgabe:

Nun kommen wir zu einem weiteren schönen Zauber.

main = putStrLn (show (sum [1,2,3,4]) )

Ausgabe

Also die Summe der Zahlen in der Liste. Es ist schön, dass es sum gibt. Aber es geht noch allgemeiner.

main = putStrLn (show (foldl (+) 0 [1,2,3,4]) )

Liefert dasselbe Ergebnis. Aber wir können so auch alle Zahlen multiplizieren.

main = putStrLn (show (foldl (*) 1 [1,2,3,4]) )

Ausgabe

Wie funktioniert das? foldl ist eine Funktion. Sie bekommt drei Eingaben. Die zweite ist ein Startwert und die dritte eine Liste. Aber die erste Eingabe von foldl ist selbst wieder eine Funktion. Die Funktion nimmt zwei Eingabeparameter und erzeugt einen Ausgabewert. die Funktionen (+) und (*) sind gerade Funktionen dieser Art. Was tut nun foldl? Es nimmt den Startwert, also 1, es nimmt das erste Element der Liste, also wieder 1. Dann wendet es die Funktion auf diese beiden Werte an. Also 1*1. Das ist 1. Dann nimmt es diese 1 als neuen Startwert, dann nimmt es das zweite Element der Liste, also 2 und wendet auf diese beide die Funktion an als 1*2. Das ist 2. Also ist 2 der neue Startwert. Dann nimmt sie das nächste Element aus der Liste, also 3. Wendet die Funktion an 2*3. Macht 6. Dann kommt die 4. Also 6*4. Macht 24. Und das ist gerade 1*2*3*4.

Mehr über eigene Funktionen

myFunction= \x -> x*2
main = putStrLn (show (myFunction 13) )

Liefert das Ergebnis 26. Es gibt aber noch eine alternative Syntax.

myFunction x = x*2
main = putStrLn (show (myFunction 13) )

Liefert dasselbe Ergebnis. Der Eingabeparameter x steht hier vor dem Gleichheitszeichen und der Ausgabeterm hinter dem Gleichheitszeichen. Der Backslash \ und der Pfeil -> werden bei dieser Notation nicht verwendet. Diese Notation kann aber noch mehr. Man kann unterschiedliche Ausgabeterme für unterschiedliche Eingaben angeben.

toString 1 = "Eins"
toString 2 = "Zwei"

main = putStrLn ( (toString 1 )++" "++(toString 1 )++" "++ (toString 2 ))

Ausgabe

Eins Eins Zwei

Auch hier kann man sich die Auswertung des Ausdrucks (toString 1 ) als ersetzen durch seine Definition (die rechts vom Gleichheitszeichen bei toString 1 steht), nämlich "Eins" vorstellen. Das ganze geht natürlich auch etwas eleganter:

toString 1 = "Eins"
toString 2 = "Zwei"

numbers = [1,1,2]

main = putStrLn (show (map toString numbers) )

Ausgabe

["Eins","Eins","Zwei"]

Selbstdefinierte Datentypen

Versuchen wir mal eine gemischte Liste.

main = putStrLn (show [1,2,"a","b"])

Das lässt sich nicht kompilieren. Elemente einer Liste müssen alle den gleichen Typ haben. 1 und 2 sind Zahlen und "a" und "b" sind Zeichenfolgen (Strings). Auch in Java und C++ müssen die Elemente eine Liste alle den gleichen Typ haben, aber in Python sind inhomogene Listen erlaubt. Wie bekommen wir es nun hin, dass wir eine inhomogene Liste gebaut kriegen. Wir definieren uns einen eigenen Datentypen, der sowohl Strings als auch Zahlen (hier nehmen wir Integer, also ganze Zahlen) tragen kann.

data MyType= MyString String | MyInteger Integer
    deriving Show

main = putStrLn (show [MyInteger 1, MyInteger 2,MyString "a",MyString "b"])

Die Ausgabe ist

[MyInteger 1,MyInteger 2,MyString "a",MyString "b"]

Das ist zwar nicht sonderlich elegant, aber wir haben eine Liste die sowohl Integer als auch Strings enthält. Wir haben den Datentypen MyType definiert und nun einer Liste, die aus Elementen vom Typ MyType besteht. Ein MyType trägt jedoch entweder einen String oder einen Integer. Irgendwie sieht es so aus, als würden wir nur den String [MyInteger 1, MyInteger 2, MyString "a",MyString "b"] ausgeben, der ja genauso in unserem Quelltext steht. Deswegen noch ein kurzes Beispiel, das zeigt, dass es sich tatsächlich um eine Liste handelt:

data MyType= MyString String | MyInteger Integer
    deriving (Show)

main = putStrLn (show ([MyInteger 1, MyInteger 2] ++ [MyString "a",MyString "b"]))

Die Ausgabe ist dieselbe, aber der Compiler konnte hier nicht mehr schummeln, es ist also tatsächlich eine Liste.

Unsere gemischte Liste sieht nun in der Ausgabe noch etwas seltsam aus. Eigenlich wollen wir etwas in der Form

[1,2,"a","b"]

Man kann dies sehr einfach durch folgende Schreibweise bewerkstelligen


data MyType= MyString String | MyInteger Integer
    deriving Show


toString (MyInteger i)= show i
toString (MyString s)=s

main= putStrLn (show (map toString   [MyInteger 1, MyInteger 2,MyString "a",MyString "b"]))

Ausgabe

["1","2","a","b"]

Wir können auf der linken Seite des Gleichheitszeichens also nicht nur Konstanten angeben, sondern auch Parameter variabel lassen. Das i bei toString (Integer i). Wenn wir toString (Integer 42) aufrufen. Dann haben wir auf der rechten Seite des Gleichheitszeichens show 42. i bekommt also den Wert 42. Man sagt auch, i wird an 42 gebunden.


data MyType= MyString String | MyInteger Integer
    deriving Show


toString (MyInteger i)= show i
toString (MyString s)=s

main= putStrLn (toString (MyInteger 42))

Ausgabe

Es ist natürlich etwas unbequem immer toString aufrufen zu müssen. Man kann dies schöner lösen, indem man sagt, wie die Funktion show auf Dinge vom Typ MyType wirken soll.

data MyType= MyString String | MyInteger Integer

instance Show MyType where
    show (MyInteger i) = show i
    show (MyString s) = show s

toString (MyInteger i)= show i
toString (MyString s)=s

main= putStrLn (show  [MyInteger 1, MyInteger 2,MyString "a",MyString "b"])

Ausgabe

[1,2,"a","b"]

Jetzt sieht die Liste genau so aus, als wäre sie eine gemischte Liste gewesen. Wir haben im Vergleich zu den anderen Beispielen die Zeile deriving Show weggelassen. Aber dafür haben wir die Zeile instance Show MyType where und folgende hinzugefügt und damit genau erklärt, wie show wirken soll.

Eine andere Syntax für Listen

Für Listen gibt es noch eine alternative Syntax.

main = putStrLn (show (1:2:3:[]))

Ausgabe

[1,2,3]

Wir können also anstelle von [1,2,3] auch schreiben (1:2:3:[]) wobei man unter günstigen Bedingungen die runden Klammern auch weglassen kann 1:2:3:[]. Dabei steht [] für die Leere Liste. Die Zeilenfolge 3:[] bedeutet in etwa. Nimm die 3 und füge sie vorne an die leere Liste an. Das ergibt dann die Liste die 3 und sonst nichts enthält also [3]. Genauso kann man an diese Liste vorne eine 2 anfügen also 2:[3]

main = putStrLn (show (2:[3]))

Ausgabe

[2,3]

Entsprechend sind also [1,2,3] und 1:[2,3] dasselbe. Man kann nun [2,3] in diesem Ausdruck durch 2:[3] ersetzen. Also ist 1:[2,3] dasselbe wie 1:2:[3] und das ist dasselbe wie 1:2:3:[]. Es gilt also [1,2,3]==1:2:3:[]. Dies bejaht auf Nachfrage sogar Haskell selbst

main = putStrLn (show ([1,2,3]==(1:2:3:[])))

Ausgabe

True

Die Aussage ist also wahr.

Rekursion

Dieser Abschnitt ist besonders kleinschrittig und hat besonders viele Beispiele. Wenn der Leser das Prinzip verstanden hat, kann er sofort beim nächsten Abschnitt weiterlesen und den Rest dieses Abschnitts getrost auslassen. Wenn er es trotz der vielen Beispiele nicht versteht, möge er sich bemerkbar machen, wir werden dann versuchen diesen Text geeignet umzugestalten.

Einführung

Rekursion bedeutet, dass eine Funktion sich selbst aufruft. Wir haben ja bereits viele Funktionen aufgerufen, zum Beispiel die vordefinierten Funktionen show, map, filter aber auch selbst definierte wie toString. Es gibt also eigentlich keinen Grund, warum eine Funktion sich nicht selbst benutzen sollte. Es gibt zum Beispiel so etwas

fun 1 = "Eins"
fun n = fun (n-1)

main = putStrLn (fun 2)

Ausgabe

"Eins"

Diese Funktion gibt offenbar "Eins" aus obwohl wir sie mit 2 aufrufen. Es ist aber nur definiert fun 1 = "Eins". Wie kommt es also zu solch einer Ausgabe. Naja, wir rufen fun mit dem Parameter 2 auf. Die Definition fun 1 = "Eins" passt nicht da der übergebene Parameter nicht 1 ist, er ist ja schließlich zwei. Die Definition fun n = fun (n-1) passt. Die Definition beginnt mit fun n. n ist hier eine Variable die jeden Wert annehmen kann, also insbesondere auch 2. Also wird diese Zeile mit n==2 ausgeführt. Auf der rechten Seite des Gleichheitszeichens steht also fun (2-1). Also wird nun die Funktion fun erneut aufgerufen. Diesmal mit dem Parameter 1. Jetzt passt die Definition fun 1 = "Eins". Das heisst, der Ausdruck fun (2-1) wird ausgewertet als "Eins". Daher liest sich die Definition fun 2 = fun (2-1) nun als fun 2 = "Eins". Man kann sich die einzelnen Schritte bei der Auswertung so vorstellen, Termumformung. Dabei ist das was hinter dem | steht ein Kommentar

fun 2      -- wende zweite Zeile der Definition von fun an.
fun (2-1)  -- führe subtraktion aus
fun 1      -- wende erste Zeile der Definition von fun an.
"Eins"     -- Endergebnis

Ich führe das ganze noch einmal für den Fall fun 3 vor.

fun 3      -- wende zweite Zeile der Definition von fun an.
fun (3-2)  -- führe subtraktion aus
fun 2      -- wende zweite Zeile der Definition von fun an.
fun (2-1)  -- führe subtraktion aus
fun 1      -- wende erste Zeile der Definition von fun an.
"Eins"     -- Endergebnis

Eine etwas sinnvollere Anwendung ist das Summieren mittels Rekursion. Es geht darum die Summe aller Zahlen bis zu einer Zahl k zu bilden.

gauss 0 b = b
gauss a b = gauss (a-1) (b+a)

main = putStrLn (show (gauss 2 0))

Ausgabe

Auch hier kann man sich die Einzelnen Schritte wieder im Detail anschauen.

gauss 2           -- wende zweite Zeile der Definition von gauss an.
gauss (2-1) (0+2) -- führe subtraktion und addition aus
gauss 1 2         -- wende zweite Zeile der Definition von gauss an.
gauss (1-1) (2+1) -- führe subtraktion und addition aus
gauss 0 3         -- wende erste Zeile der Definition von gauss an.
3                 -- "Endergebnis"

Listen und Rekursion

Die Möglichkeit, einige Parameter variabel zu lassen, klappt auch für Listen.

fun (1:2:x)= show x

main = putStrLn (fun [1,2,3,4])

Ausgabe

[3,4]

Hier wird also die Variable x an die Liste [3,4] gebunden. Wir haben also festgelegt, dass die Liste mit 1:2 beginnen muss und dann irgendwas kommen kann. Und dieses Irgendwas wird dann zu x. Man kann zum Beispiel so auch das erste Element einer Liste ausgeben.

fun (a:b)= show a

main = putStrLn (fun [1,2,3,4])

Ausgabe

Oder aber alle Elemente bis auf das erste.

fun (a:b)= show b

main = putStrLn (fun [1,2,3,4])

Ausgabe

[2,3,4]

Jetzt kann man aber auch die Elemente einer Liste verarbeiten. So zum Beispiel

fun (a:b)= (10+a):(fun b)
fun []=[]
main = putStrLn (show (fun [1,2,3,4]))

Ausgabe

[11,12,13,14]

Wir haben also auf jedes Element der Liste 10 addiert. Das ist wohl die Stelle (10+a). Im Code steht ferner ein Doppelpunkt im Befehl (10+a):(fun b). Die Funktion fun liefert also eine zusammengesetzte Liste zurück. Der Doppelpunkt hat dieselbe Bedeutung wie in 1:[2] Auf der rechten Seite des Doppelpunktes steht immer eine Liste. In diesem Fall ist das die Liste (fun b). Es wird also die Funktion fun mit dem Argument b aufgerufen und diese Funktion gibt eine Liste zurück. (a+10) wird dann vorne an die Liste angehängt. Und diese neue Liste ist das Ergebnis. Als Beispiel betrachten wir fun [1,2,3,4]. Das führt zu a==1 und b==[2,3,4]. Der Rückgabewert von fun [2,3,4] ist [12,13,14]. Also wird aus dem Befehl (10+1):([12,13,14]. Das ist einfach [11,12,13,14]. Also ist die Ausgabe ebenfalls [11,12,13,14]. Jetzt kann man sich fragen, warum fun [2,3,4] den Rückgabewert [12,13,14] hat. Nun das ist dieselbe Begründung mit a==2 und b==[3,4]. Genauso ergibt sich der Rückgabewert von fun [3,4]. Interessant wird es bei fun [4]. Hier gilt offenbar a==4 und b ==[]. Also wird wegen (fun b), die Funktion fun mit dem Argument [] aufgerufen. Es gibt natürlich die Zeile fun []= []. Und damit ist klar, dass fun die leere Liste zurückgeben soll. Man kann sich nun fragen, ob die Zeile fun (a:b)= (10+a):(fun b) hier irgendwelche Schwierigkeiten bereiten kann. Sie tut das nicht, weil durch a:b klar ist, dass zwei Dinge gemeint sind, also mindestens ein Listenelement, das vorne an einer (ggfs. leeren) Liste angehängt ist. Die leere Liste ist jedoch eine einzelne Sache, und es gibt nicht, was vorne an ihr dranhängt. Daher wir diese Zeile als unpassend verworfen und nicht berücksichtigt. Auch hier führe ich der Übersicht halber noch mal die einzelnen Schritte vor

fun [1,2,3,4]                              -- verwende die erste Zeile der Definition von fun.
(10+1):(fun [2,3,4])                       -- verwende die erste Zeile der Definition von fun
(10+1):((10+2):(fun [3,4]))                -- verwende die erste Zeile der Definition von fun
(10+1):((10+2):((10+3):(fun [4])))         -- verwende die erste Zeile der Definition von fun
(10+1):((10+2):((10+3):((10+4):(fun [])))) -- verwende die zweite Zeile der Definition von fun
(10+1):((10+2):((10+3):((10+4):([]))))     -- führe Addition in den inneren Klammern aus.
11:(12:(13:(14:([]))))                     -- Klammern um  [] können weg
11:(12:(13:(14:[])))                       -- führe Doppelpunktoperation (vorne an Liste anfügen) aus
11:(12:(13:([14])))                        -- Klammern um [14] können weg.
11:(12:(13:[14]))                          -- führe Doppelpunktoperation (vorne an Liste anfügen) aus
11:(12:[13,14]])                           -- Klammern um [13,14] können weg.
11:(12:[13,14])                            -- führe Doppelpunktoperation (vorne an Liste anfügen) aus
11:([12,13,14])                            -- Klammern um [12,13,14] können weg.
11:[12,13,14]                              -- führe Doppelpunktoperation (vorne an Liste anfügen) aus
[11,12,13,14]                              -- Endergebnis

Ein weiteres Beispiel ist wohl ganz angebracht. Man kann das letzte Element einer Liste bestimmen.

fun (a:[])= show a
fun (a:b)= fun b

main = putStrLn (fun [1,2,3,4])

Ausgabe

Das letzte Element hat offenbar die Form a:[] und das soll zurückgegeben werden. Durch die Zeile fun (a:b)= fun b wird dafür gesorgt, dass der Rest der Liste durchsucht wird, sofern a:[] nicht gepasst hat. Interessant ist der Fall [4]. Das ist ja gerade 4:[]. Also passt hier sowohl a:[] als auch a:b. Die Regel besagt, dass in solchen Fällen das im Quelltext weiter oben stehende Pattern, hier also a:[] verwendet und alle anderen verworfen werden. Auch hier gebe ich noch einmal die einzelnen Schritte zu Auswertung an.

fun [1,2,3,4]  -- zweite Zeile der Definition von fun
fun [2,3,4]    -- zweite Zeile der Definition von fun
fun [3,4]      -- zweite Zeile der Definition von fun
fun [4]        -- erste Zeile der Definition von fun, denn es ist ja 4:[]==[4]
4              -- Endergebnis

Ein weiteres Beispiel ist die Bestimmung der Anzahl der Elemente einer Liste.

fun ([]) c= show c
fun (a:b) c= fun b (c+1)

main = putStrLn (fun [11,12,13,14] 0)

Ausgabe

Hier hat die Funktion fun zwei Eingabeparameter. Der erste ist eine Liste. Der zweite ist eine Zahl, die als Zähler verwendet wird. Bei jedem Schritt wird das jeweils erste Element der Liste entfernt und der Zähler um 1 erhöht. Ist die Liste schließlich leer, so wird der Wert des Zählers zurückgegeben.

Auch hier noch einmal die einzelnen Schritte.

fun [11,12,13,14] 0   -- Zweite Zeile der Definition von fun 
fun [12,13,14] (0+1)  -- Addition ausführen
fun [12,13,14] 1      -- Zweite Zeile der Definition von fun
fun [13,14] (1+1)     -- Addition ausführen
fun [13,14] 2         -- Zweite Zeile der Definition von fun
fun [14] (2+1)        -- Addition ausführen
fun [14] 3            -- Zweite Zeile der Definition von fun   
fun [] (3+1)          -- Addition ausführen    
fun [] 4              -- erste Zeile der Definition von fun
4                     -- Endergebnis

if then else

Wir haben ja bereits oben Möglichkeiten kennengelernt eine Funktion für verschiedene Eingabewerte unterschiedlich zu definieren. Das Konstrukt if then else bietet heirzu noch eine weitere Möglichkeit. Ein Beispiel

fun a= if a<10 then "Ja" else "Nein"

main = putStrLn (fun 5)

Ausgabe

Ja

Was passiert also im einzelnen. Es wird fun mit dem Parameter 5 aufgerufen. Dann wird die Bedingung a<10 ausgeführt. In unserem Falle 5<10. Die Aussage 5<10 ist eine im mathematischen Sinne wahre Aussage. Also gilt die Bedingung als erfüllt. Weil die Bedingung erfüllt ist, wird die Definition, die zwischen then und else steht, ausgewertet. In diesem Falle ist das "Ja". Das heißt, der Ausdruck if 5<10 then "Ja" else "Nein" wird ausgewertet als "Ja". Damit wird auch fun 5 ausgewertet als "Ja". Und das wird dann durch putStrLn ausgegeben. Noch einmal die einzelnen Schritte

fun 5                           -- Wende Definition von fun an.
if 5<10 then "Ja" else "Nein"   -- Werte Ausdruck 5<10 aus.
if True then "Ja" else "Nein"   -- Nimm definition bei then
"Ja"                            -- Endergebnis

Das Wort True bedeutet wahr. Man sagt auch der Ausdruck 5<10 wird ausgewertet zu True. dasselbe Beispiel mit anderem Parameter

fun a= if a<10 then "Ja" else "Nein"

main = putStrLn (fun 15)

Ausgabe

Nein

Auch hier noch mal die einzelnen Schritte

fun 15                           -- Wende Definition von fun an.
if 15<10 then "Ja" else "Nein"   -- Werte Ausdruck 5<10 aus.
if False then "Ja" else "Nein"   -- Nimm definition nach else
"Nein"                           -- Endergebnis

False bedeutet Falsch. Die Aussage 15<10 ist im mathematischen Sinne falsch. Man sagt auch der Ausdruck 15<10 wird ausgewertet zu False. Ist die Bedingung in einer if then else Konstruktion (hier also 15<10 ) nicht erfüllt (wird sie also zu False ausgewertet), so wird die Definition nach else verwendet. In diesem Falle also Nein.

Ein weiteres Beispiel:

fun a= if a<2 then "Ja" else "Nein"

main = putStrLn (show (map fun [0,1,2,3,4]))

Ausgabe:

["Ja","Ja","Nein","Nein","Nein"]

map und filter im Eigenbau

Jetzt haben wir genügend werkzeuge um uns die Funktionen map und filter selber schreiben zu können.

map

mymap f (x:xs)= (f x):(mymap f xs)
mymap f []= []

main= putStrLn (show (mymap (+10) [1,2,3,4]))

Ausgabe

[11,12,13,14]

Filter

myfilter f (x:xs)= if f x then x:(myfilter f xs) else myfilter f xs
myfilter f []= []

main= putStrLn (show (myfilter (<3) [1,2,3,4]))

Ausgabe

[1,2]

Monaden

Monaden sind was schönes. Eigentlich auch ganz einfach, aber blöderweise schwer zu lernen. Wir werden mit einem Beispiel, das wir bereits kennen, beginnen. Nämlich der Liste. Die Liste ist nämlich ein Beispiel für eine Monade. Eine Liste ist ein Container. Konkret ist [1,2,3] eine Liste, in die die Ganzzahlen (Integer) 1,2 und 3 hineingesteckt wurden. Man kann aber den selben Container auch verwenden, um andere Dinge hineinzustecken. So zum Beispiel ["Eins","Zwei","Drei"]. Hier haben wir Zeichenfolgen in den Container gesteckt. Es gibt aber noch andere Container, zum Beispiel Maybe. Ein Maybe Container enthält entweder genau eine Sache oder Nichts. Wenn er einen String enthalten soll schreibt man zum Beispiel Just "meinString", bei einer Ganzzahl schreibt man Just 42, und wenn er gar nichts enthalten soll schreibt man einfach Nothing. Für den Listencontainer kennen wir ja bereits die Funktion map. Die gibt es aber noch in einer anderen Syntax.

fun x = return (x+10)

main= putStrLn (show ( [1,2,3] >>= fun))

Ausgabe

[11,12,13]

Die Funktion, die wir auf die Liste anwenden wollen, ist fun. Die Anwendung geschieht diesmal nicht mit der Funktion map, sondern mit dem gefährlich aussehenden Operator >>=, der auf den Namen bind hört. Auffällig ist noch, dass wir in der Definition von fun die Funktion return benutzen. Ansonsten sieht aber alles genauso aus wie bei map.

Das schöne bei dieser Syntax ist das sie ohne Änderung auch für andere Kontainer funktioniert. Hier zum Beispiel der Maybe Container, mit Just

fun x = return (x+10)

main= putStrLn (show ( (Just 7) >>= fun))

Ausgabe

Just 17

Wir können also Programme schreiben die unabhängig vom gewählten Container laufen, eine praktische Eigenschaft. ^[1].

Jetzt ist natürlich klar das bind und retrun unterschiedliche Funktionen sein müssen, in abhängigkeit davon ob wir sie im Bezug auf Maybe oder im Bezug auf die Liste anwenden wollen. Das macht die Sache etwas unverständlich. Wir haben also die Funktion return für Listen und die Funktion return für Maybe und diese sind völlig unterschiedlich und trotzdem schreiben wir für beide return. Das ist sehr störend weil man es von der Schule her gewohnt ist unterschiedliche Dinge unterschiedlich zu bezeichnen. Hier bezeichnen wir aber unterschiedliche Dinge mit dem gleichen Namen. Dennoch tun diese beiden unterschiedlichen Funktionen etwas ähnliches. Sie haben in Verbindung mit bind eine ähnliche Wirkung wie map auf Listen wie wir im obigen Beispiel gesehen haben. Diese Tatsache wird in Haskell mit der Sprechweise die Liste und Maybe sind beides Monaden Rechnung getragen. Diese Sprechweise kann man präzisieren in dem man sagt das eine Monade mindestens die Funktion return und den Operator bind besitzen muss. Ferner wir gefordert das gewisse Verkettungen dieser Operatoren gewisse Ergebnisse liefern. Aber dazu später mehr.

Hier erst noch einmal ein weiteres Beispiel

kunden= [
  ("David Maier",[
    ("Adresse", [
      ("Strasse","Auf dem Holzweg"),
      ("Ort", "Niemandsheim"),
      ("Hausnummer","23")]),
    ("Telephon", [
      ("LaenderKennzahl","49"),
      ("Ortnetzkennzahl","4227"),
      ("Teilnehmerrufnummer","666")]
    )]
  )]

main= putStrLn (show ((lookup "David Maier" kunden) >>= lookup "Adresse" >>= lookup "Ort" ))

Ausgabe

Just "Niemandsheim"

Wir haben also eine Suchanfrage an eine Baumstruktur gestellt und eine Antwort erhalten. Die Funktion Lookup liefert den gefragten Teilbaum zurück. Mit dem bind Operator >>= können wir solche Abfragen verketten.

Was geht hier vor?

Erst berechnen wir lookup "David Maier" kunden, das ergibt

Just [("Adresse", [
      ("Strasse","Auf dem Holzweg"),
      ("Ort", "Niemandsheim"),
      ("Hausnummer","23")]),
    ("Telephon", [
      ("LaenderKennzahl","49"),
      ("Ortnetzkennzahl","4227"),
      ("Teilnehmerrufnummer","666")]
    )]

Dieses große Konstrukt nenne ich k. Es ein der Maybe Kontainer. Der eine Baumstruktur enthält. Jetzt berechnen wir lookup "Adresse". Das ist erst mal ein Problem, denn lookup braucht zwei Eingabeparameter. Der zweite fehlt also. Haskell sagt jetzt einfach lookup "Adresse" ist eine neue Funktion, die genau einen Eingabeparameter hat. Diese nennt ich mal f. Jetzt wird k >>= f berechnet. Es wird also f auf k den Inhalt von k angewendet. Das ergibt dann

Just [
      ("Strasse","Auf dem Holzweg"),
      ("Ort", "Niemandsheim"),
      ("Hausnummer","23")
     ]

Dann kommt dasselbe Spiel mit lookup "Adresse". Das führt dann zum angegebenen Endergebnis.

Wenn zwischen drin eine der Abfragen fehlschlägt kommt einfach Nothing zurück. Wie im nächsten Beispiel.

kunden= [
  ("David Maier",[
    ("Adresse", [
      ("Strasse","Auf dem Holzweg"),
      ("Ort", "Niemandsheim"),
      ("Hausnummer","23")]),
    ("Telephon", [
      ("LaenderKennzahl","49"),
      ("Ortnetzkennzahl","4227"),
      ("Teilnehmerrufnummer","666")]
    )]
  )]

main= putStrLn (show ((lookup "David Maier" kunden) >>= lookup "Unsinn" >>= lookup "Ort" ))

Ausgabe

Nothing

Im Fehlerfalle bricht also nicht alles zusammen, und es kommt auch kein undefiniertes Ergebnis zurück, es wird vielmehr zurückgegeben, dass Nichts berechnet werden konnte. Das ist auch praktisch wenn man es mit irgendwelche Berechnungen zu tun hat, die fehlschlagen können. Man bekommt somit im Misserfolgsfalle ein klares NichtErgebnis.

Theoretische Details

Ich will noch einmal versuchen, etwas weniger anschaulich und dafür auch etwas richtiger, zu erklären, was es mit dem Operator bind >>= und der Funktion return auf sich hat. Es gibt einen Containertypen. Die Funktion return nimmt ein beliebiges Ding und gibt einen Container zurück, der dieses Ding enthält. Der Operator bind m >>= f nimmt einen Container m samt Inhalt und eine Funktion f, die den Inhalt des Containers m entgegennehmen kann und gibt einen Container vom selben Typ zurück, der einen ggf. völlig anderen Inhalt als m hat. Insbesondere haben der Eingangscontainer m und der Rückgabecontainer von f den selben Containertyp. Der Typ des Inhalts von m kann aber völlig anders sein, als der Typ des Rückgabecontainers von f. Der bind Operator hat also zwei Eingabeparameter, einen Container und eine Funktion zum Verarbeiten des Inhalts des Containers. Der bind Operator gibt einen Container zurück. Dieser hat den selben Containertyp wie der der Eingabecontainer m und der Rückgabecontainer von f. Ferner hat der Inhalt der Rückgabecontainers den selben Typ wie Inhalt des Rückgabecontainers von f. Bislang habe ich in diesem Tutorial die falsche Vorstellung verbreitet, dass bind den Inhalt aus m herausnimmt, ihn an f übergibt und das Ergebnis zurückgibt. Was Typen angeht, wäre das ja auch richtig. Und auch das in den Beispielen gezeigte Verhalten wäre so zu erklären. In Wahrheit gibt es aber keine Funktion, mit der man Dinge wieder aus einem Container herausnehmen kann. Warum es die nicht gibt, habe ich selber noch nicht verstanden, es gibt aber sicherlich Fälle wie IO, in denen eine solche Funktion nicht möglich bzw. sinnvoll ist. Da es aber keine Herausnehmfunktion gibt, veranstaltet man eine ziemlich auswendige Konstruktion, um etwas Ähnliches bewerkstelligen zu können. Man transformiert f auf eine höhere Ebene und erhält eine Funktion g. Die Funktion g ist in der Lage m direkt entgegen zu nehmen. Dafür gibt sie jedoch einen Container zurück der den Rückgabewert von f enthält. Wir erinnern uns, dass f jedoch selbst bereits einen Container samt Inhalt zurückliefert. Die Anwendung von g auf m liefert also einen Container zurück, der wiederum einen Container enthält, der einen Inhalt enthält. Nun gibt es eine weitere Funktion, genannt join, die diesen Doppelcontainer mit Inhalt wieder auf einen einzigen Container mit Inhalt abbildet, und diesen gibt bind dann schließlich zurück.

↑ In Java oder C++ hätten wir Generics oder Templates verwendet um dasselbe zu erreichen, hier haben wir keinen einzigen Typen hingeschrieben, und trotzdem haben wir volle Typenprüfung zur Kompilezeit

Monaden noch etwas korrekter

Jetzt zwei Jahre später kann ich endlich besser formulieren, was eine Monade ist. Eine Monade ist etwas, was die Mondengesetze erfüllt, nicht mehr und nicht weniger. Das ist aber eine Sprechweise, die fast ausschließlich für Mathematiker geeignet ist. Und genau das macht es so schwer, sie zu verstehen. Als erstes brauchen wir eine Abbildung von Typen auf Typen. Das ist ein ziemlich abgedrehtes Konzept. Eine normale Funktion nimmt eine Variable entgegen und gibt eine Variable zurück. Die Variablen haben Typen. So zum Beispiel sind 2.4 und 56.78 Variablen vom Typ (beispielsweise) Double. Und 42 und 23 Variablen vom Typ (beispielsweise) Integer. Eine Funktion, die 2.4 entgegen nimmt und 23 zurück gibt, ist eine Abbildung, die Double-Werte auf Integer-Werte abbildet. Kurz sie bildet ab von Double nach Integer. Nun packen wir Double, Integer, String und was es sonst noch gibt (und das ist so einiges), in eine Typenmenge T zusammen. Wohlgemerkt 23 und 42 sind keine Elemente von T, aber Integer und Double sind Elemente von T. Jetzt betrachteten wir eine Funktion von T nach T. Sie nimmt also einen Typen entgegen und gibt einen Typen zurück. Aus objektorientierten Sprachen wie Java C# oder C++ ist das Konzept als Generics bzw. Templates bekannt.

List<Integer>

bezeichnet eine Liste von Integern. List selber bildet den Typen Integer auf den Typen List<Integer> ab. List ist also eine Abbildung von T nach T und man nennt sie auch eine Typenkonstruktor. Das hat nichts mit dem Konstruktor aus der objektorientierten Programmierung zu tun, der Begriff klingt lediglich ähnlich.

Eine Monade Besteht aus einem Typenkonstruktor M. Und zwei Funktionen. Die Anwendung des Typenkonstruktors aus einen Typen notieren wir (hier am Beispiel Integer) wie folgt

M Integer

Natürlich können wir auch Variablen die Werte aus T annehmen verwenden. Wir nennen sie üblicher weise a , b usw. Die Anwendung von M auf die Typenvariable a notieren wir als

M a

Wohlgemerkt a ist ein Typ und keine Variable. Also a kann für Integer String oder Double stehen nicht jedoch für 2.4 66 oder "Hallo Welt". Und die Auswertung dieses Ausdrucks ergibt wiederum einen Typen. Nun besagt eine Monadengesetz dass es für jeden Typen a je eine Abbildung von a nach M a geben muss. Diese bezeichnet man überlicherweise mit dem Namen return. Das ist nicht zu verwechseln mit dem Schlüsselwort return in vielen Programmiersprachen und hat damit auch wirklich überhaupt rein gar nichts zu tun und man stelle sich bei Schwierigkeiten vielleicht besser vor das sie einen anderen Namen hätte. Für den og. Sachverhalt schreibt man kurz

return :: a- > M a

Man kann sich die als "return ist eine Funktion von a nach M a" ausgesprochen vorstellen. Return nimmt wiederum konkrete Werte entgegen. Also 24 oder 23.5 usw. Und gibt auch konkrete Werte zurück. Sie haben den Typ M a. Die Monadengesetze fordern noch eine weitere Funktion. Sie heißt bind und nimmt zwei Dinge entgegen. Das erste ist von Typ M a. Das zweite ist eine Funktion die a auf M b abbildet. Die Funktion bind gibt einen einen Wert vom Typ M b zurück. Man schreibt hierfür kurz.

bind :: M a -> (a -> M b) -> M b

Dabei ist

M a

der Typ des ersten Parameters der bind übergeben wird. Und

a -> M b

der des zweiten Parameters. Man schreibt bind auch >>= als infix Operator. Das heißt die Schreibweisen

bind x f
x >>= f

sind äquivalent. Weiterhin fordern die Mondengesetze die Einhaltung gewisser Regeln. Es muss immer gelten.

(x  >>= return) == x
(return x) >>= f == f x
((x >>= f) >>= g) == x>>= (\y-> (f y) >>=g)

Demnach ist jeder Typenkonstruktor mit den beiden zugehörigen Funktionen, die die o.g. Gesetze erfüllen eine Monade. Das sind mit unter sehr unterschiedliche Dinge. Wichtige Beispiele die ich hier nur dem Namen nach angebe sind Either, Maybe, List, State, Reader, Writer, Parsec. Interessant ist hier zum Beispiel List. Es gibt Berechnungen die keine oder mehrere Ergebnisse des selben Typs zurück liefern können. Zum Beispiel die Nullstellenbestimmung bei Polynomen, oder die Zugmöglichkeiten bei Brettspielen wie z.B. Mühle oder Schach. Es gibt Berechnungen die lesbare und oder schreibbare Variablen die an allen Stellen der Berechnung zugänglich sind benötigen. Hierfür gibt es die Reader Write und State Monaden. Es gibt Parser die verschiedene Muster in einem Eingabestring hintereinander ausprobieren. Hierfür gibt es den monadischen Parser Parsec.

[1] In Java oder C++ hätten wir Generics oder Templates verwendet um dasselbe zu erreichen, hier haben wir keinen einzigen Typen hingeschrieben, und trotzdem haben wir volle Typenprüfung zur Kompilezeit

[1]