Dieses Dokument enthält Informationen zur benötigten Software für diesen Kurs, eine kurze Einführung in Haskell mit Code-Beispielen und Hinweise bezüglich der Abgabe von Arbeitsblättern.
Zum Ausführen von Haskell-Code wird der Glasgow Haskell Compiler (kurz GHC) benötigt. Der minimal installer ist ausreichend. Falls Sie Haskell nicht über einen Packetmanager installieren möchten, können Sie alternativ auch die Binaries auf https://www.haskell.org/ghc direkt herunterladen (Download -> Current Stable Release). Fügen Sie in diesem Fall den Pfad, in dem die Programme ghc und ghci liegen, zur path-Umgebungsvariable hinzu.
Zusätzlich wird das Programm Shrimp (spc) benötigt, um bestimmte Aufgabe zu bearbeiten. Dieses ermöglicht es, auf einfach Weise Programme als Flussdiagramme zu beschreiben, welche dann in Haskell übersetzt werden. Um sich mit der Anwendung von Shrimp vertraut zu machen, folgen Sie dem Tutorial auf der Startseite der Dokumentation.
Beim Ausführen von Shrimp-Programmen (auch sp-Programme genannt) können Ausführungsspuren (engl. traces) generiert werden, welche im CSV-Format abgespeichert werden. Zum Betrachten solcher Dateien wird ein Tabellenkalkulationsprogramm wie z.B. LibreOffic Calc empfohlen.
In der Datei AB/Examples.hs sind einige Beispiele, welche Sie testen und modifizieren können. Öffnen Sie die Datei dazu mit dem Interpreter ghci. Im Interpreter können Ausdrücke wie z.B. 2*(3+4) oder couple "abc" "123" eingegeben werden. Mit dem Befehl :r können Sie die Datei neu laden, z.B. nachdem Sie diese verändert haben und mit :q beenden Sie den Interpreter. Mit dem Befehl :t können Sie den Typ einer Funktion ausgeben lassen, z.B. :t couple. Mit einem Ausrufezeichen können Sie Befehle der Kommandozeile ausführen, z.B. :!clear (bzw. :!cls auf Windows).
Funktionen werden durch Ausdrücke definiert. Der Kontrollfluss, welcher in imperativen Sprachen durch Kontrollstrukturen (if, for, while, etc.) gesteuert werden kann, muss in Haskell mittels Rekursion realisiert werden.
Ausdrücke werden in Präfix-Notation angegeben. Ein Aufruf f(x, g(y, z), myVar) würde in Haskell als (f x (g y z) myVar) geschrieben werden. Binäre Operatoren sind zweistellige Funktionen, dessen Namen nicht aus alphanumerischen Zeichen bestehen, wie z.B. +, -, *, &&, ||, ==. Diese werden in Infix-Notation verwendet: (((3 * (2 + x)) > y) && (fun z)). Die Klammern am Anfang und Ende eines Ausdrucks können weggelassen werden, z.B. wäre f x (g y z) myVar auch in Ordnung.
Funktions- und Variablennamen fangen immer mit einem Kleinbuchstaben an. Sie dürfen auch ein Apostroph ' enthalten, sofern es nicht an erster Stelle vorkommt. Der folgende Code definiert eine Funktion f2, welche drei Eingabeparameter x, y, y' hat und y zurück gibt, falls x ungerade ist, ansonsten y'.
f2 x y y' = (if' ((mod x 2) == 1) y y')
if' hat drei Eingabeparameter und gibt den zweiten zurück, falls der erste Parameter wahr ist, ansonsten den dritten.
Eine Konstante kann als eine Funktion gesehen werden, welche keine Eingabeparameter hat. Beispiele für verschiedene Literale:
pi = 3.14 baseNo = 2 str = "a string" -- type String chr = 'x' -- type Char flag_q2 = False -- type Bool list = [2,3,5,7] -- list of numbers {- the following constant contains a 3x3 matrix with entries from 1 to 9 -} matrix = [ [1,2,3], [4,5,6], [7,8,9] ]
matrix. Jede Zeile des Ausdrucks muss aber mit mehr Leerzeichen eingerückt sein als das erste Zeichen des Funktionsnamens (in diesem Fall m). Es sollten keine Tabulatorzeichen verwendet werden. Das erste Beispiel könnte auch so geschrieben werden:
f2 x y y' = (if' ((mod x 2) == 1) y y' )
Der Typ einer einstelligen Funktion, dessen Eingabeparameter vom Typ Int ist und dessen Rückgabewert vom Typ Bool, lautet Int -> Bool. Nehmen wir an, dass in f2 die Variable x vom Typ Int und die Variablen y, y' vom Typ String sind. Dann würde die Signatur der Funktion wie folgt aussehen:
f2 :: Int -> String -> String -> String
-> getrennt und der letzte Typ ist der Typ des Rückgabewerts. Der Operator -> ist rechtsassoziativ und der obige Typausdruck wird daher als Int -> (String -> (String -> String)) interpretiert. Das heißt, f2 kann als einstellige Funktion gesehen werden, welche einen Parameter vom Typ Int hat und dessen Rückgabewert vom Typ (String -> (String -> String)) ist; der Rückgabewert ist selbst eine Funktion. Die Interpretation einer mehrstelligen Funktion als eine Reihe von einstelligen Funktionen wird als Currying bezeichnet.
Der Ausdruck (f2 1) gibt eine Funktion zurück, welcher der Funktion f2 entspricht, wobei der erste Eingabeparameter auf den Wert 1 festgelegt wird. Dies wird als partielle Applikation bezeichnet.
Falls für eine Funktion keine Signatur angegeben wird, dann versucht der Compiler bzw. Interpreter eine möglichst allgemeinen Signatur selbst abzuleiten.
Die where-Klausel erlaubt es, mehrfach vorkommende oder lange Teilausdrücke bei der Definition einer Funktion separat zu definieren.
f3 x = z where y = x + x z = y * y
y und z sind nur innerhalb der Definition von f3 gültig. Ist z.B. y bereits auf globaler Ebene definiert, dann wird die Definition aus der where-Klausel bevorzugt (shadowing). Mehrfach verschachtelte where-Klauseln sind möglich.
Mit dem Schlüsselwort type können Typaliase eingeführt werden, z.B. type Age = Int. Ein Alias wird identisch behandelt wie der Typausdruck auf der rechten Seite. Jedes Vorkommen von Age kann durch Int ersetzt werden und andersherum, ohne die Semantik des Programms zu beeinflussen.
Ein Datentyp in Haskell besteht aus einem Namen und mindestens einem Konstruktor. Ein Konstruktor beschreibt wie ein Datentyp repräsentiert wird. Ein Konstruktor besteht aus einem Namen und einer Reihe von Typausdrücken. Zum Beispiel kann eine Farbe mittels RGB oder HSV repräsentiert werden. In beiden Fällen werde drei Werte benötigt, welche als Float ausgedrückt werden können.
data Color = RGB Float Float Float | HSV Hue Saturation Value type Hue = Float -- [0°,359°] = [0.0,1.0] type Saturation = Float -- [0%,100%] = [0.0,1.0] type Value = Float -- [0%,100%] = [0.0,1.0] black = RGB 0.0 0.0 0.0 black' = HSV 0.5 0.6 0.0 red = RGB 1.0 0.0 0.0 red' = HSV 0.0 1.0 1.0
Bezeichner von Datentypen und Konstruktoren beginnen stets mit einem Großbuchstaben. Dadurch können Sie von Variablen- und Funktionsbezeichnern unterschieden werden. Ein Konstruktor kann den gleichen Namen haben wie der Datentyp (üblich, wenn es nur einen Konstruktor gibt). Mit Typaliasen kann man dokumentieren, welche Art von Wert man an welcher Stelle des Konstruktors erwartet, wie im obigen Beispiel für HSV. Ein Konstruktor kann wie eine Funktion aufgerufen werden, um einen Wert zu definieren.
Mittels Pattern Matching kann auf die Werte eines Konstruktors zugegriffen werden.
Ein Pattern ist ein Ausdruck, der auf der rechten Seite von = vorkommt und nur aus Konstruktoren und Variablen besteht. Ein Pattern beschreibt eine Menge von Werten, die eine gewisse Struktur aufweisen (z.B. Listen mit mindestens zwei Elementen) und kann Teile dieser Strukturen an Variablen binden (z.B. "sei y das zweite Element der Liste").
redVal (RGB x _ _) = x --redVal red == 1.0 swapRedBlue (RGB r g b) = (RGB b g r)
redVal gibt den Rot-Farbwert eines Werts vom Typ Color zurück, welcher mittels des Konstruktors RGB definiert wurde. Die Unterstriche stehen dafür, dass die Werte an diesen Stellen nicht benötigt werden. Der Ausdruck redVal red' würde zur Fehlermeldung Non-exhaustive patterns führen, da die Funktion nicht definiert ist für den Konstruktor HSV. Man könnte eine weitere Zeile redVal (HSV h s v) = ... hinzufügen, welche den Rotwert aus der HSV-Repräsentation berechnet.
Ein Konstruktor kann auch ganz allein ohne Typausdrücke vorkommen. Zum Beispiel ist der Datentyp Bool definiert als data Bool = True | False. Ein Datentyp der nur aus Konstruktoren ohne Typausdrücke besteht, kann als Enumeration gesehen werden. Entsprechend kann über Pattern Matching eine Fallunterscheidung vorgenommen werden, je nachdem ob eine Variable vom Typ Bool wahr oder falsch ist.
if' True x y = x if' False x y = y
Listen haben zwei spezielle Konstruktoren [] und :. Auf der rechten Seite vom = ist der Ausdruck (2:[3,4,5]) gleichbedeutend mit prepend 2 [3,4,5], was [2,3,4,5] ergibt. Auf der linken Seite als Pattern haben sie folgende Bedeutung:
(x:xRest) — falls die Liste aus mindestens einem Element besteht, dann sei x das erste Element und xRest die Liste ohne das erste Element[] — falls die Liste leer ist(x:[]) — falls die Liste aus genau einem Element besteht, dann sei x dieses Element[x] — gleichbedeutend mit (x:[])listTest [x,y] = "list with exactly two elements" listTest (x:(y:z)) = "list with at least two elements" listTest z = "all other cases"
listTest werden die Patterns der Reihe nach geprüft und die erste Definition gewählt, dessen Pattern passt. Zuerst wird also geprüft, ob die Liste genau zwei Elemente hat, danach, ob sie mindestens zwei hat und in allen anderen Fällen wird die dritte Definition gewählt. Würde man die erste und dritte Zeile vertauschen, würde die Funktion immer "all other cases" zurückgeben.
Eine Typklasse beschreibt eine Menge von Typen, für die bestimmte Funktionen definiert sind. Zum Beispiel können zwei Werte des Typs Int oder Float beide mit der Funktion < verglichen werden. Dies ist möglich, weil beide Typen Mitglieder der Typklasse Ord (von ordered) sind. Mitglieder dieser Typklasse müssen die Funktionen <, <=, >, >= definieren.
Typklassen sind ähnlich zu Interfaces in anderen Programmiersprachen.
Mitglieder der Typklasse Eq (von equal) müssen die Funktionen == und /= definieren. Bis auf Funktionstypen (Typen der Form * -> *) sind alle Typen, welche in dem Kurs genutzt werden, Mitglieder von Eq und können daher auf Gleichheit geprüft werden.
Mitglieder der Typklasse Show können mittels der Funktion show in eine String umgewandelt werden. Mitglieder der Typklasse Read können mittels der Funktion read von einem String zurück umgewandelt werden. Der Rückgabetyp muss dabei angegeben werden, z.B. ( (read "[1,2,3]") :: [Int]).
Für selbst-definierte Datentypen gibt es mittels des Schlüsselwortes deriving die Möglichkeit, dass die Funktionen einer bestimmten Typklasse automatisch für diesen Typ definiert werden. Dadurch wird der selbst-definierte Typ zum Mitglied dieser Typklasse.
data Color = RGB Float Float Float | HSV Hue Saturation Value deriving (Eq,Show,Read)
Color mittels show in einen String umzuwandeln und mit read wieder zurück umzuwandeln. Da Color auch Mitglied von Eq ist, können seine Werte auch auf Gleichheit geprüft werden. Zwei Werte gelten als gleich, wenn sie mit dem gleichen Konstruktor erzeugt wurden und die einzelnen Komponenten gleich sind (red == red' wäre False).
Das Ableiten funktioniert nur, wenn alle Typausdrücke der Konstruktoren auch Mitglieder der Typklasse sind, für welche die Funktionen abgeleitet werden sollen.
Signaturen polymorpher Funktionen können mit Type Constraints ausgedrückt werden. Die Signatur einer Funktion, welche Listen mit Elementen beliebigen Typs sortiert, würde so aussehen:
mySort :: (Ord a) => [a] -> [a]
[a] steht für eine Liste mit Elementen vom Typ a, wobei a ein beliebiger Typ sein kann. Da man nur Listen sortieren kann, bei der eine Ordnung für die Elemente der Liste gegeben ist, muss a ein Mitglied der Typklasse Ord sein. Dies wird durch das Type Constraint (Ord a) => ausgedrückt.
Weitere Informationen zu Typklassen gibt es auf Haskell/Classes and types auf Wikibooks.
Mit der Funktion trace können Strings zum Debuggen ausgegeben werden. Der erste Eingabeparameter ist der String, welcher ausgegeben werden soll und der zweite Eingabeparameter ist der Rückgabewert. Ein Wert beliebigen Typs kann mit der Funktion show in einen String umgewandelt werden, vorausgesetzt dieser Typ ist ein Mitglied der Typklasse Show.
In der Datei Test.hs sind ab dem Kommentar --Tracing examples Beispiele, wie man die Funktion konkret zum Tracen einer Funktion benutzen kann. Die Reihenfolge der Trace-Ausgabe hängt von der Reihenfolge ab, in der die Ausdrücke ausgewertet werden. Aufgrund der Evaluationsstrategie von Haskell (lazy evaluation) ist diese Reihenfolge nicht ganz offensichtlich. Für reverse2 "abc" stehen die Ausgaben new res: z.B. erst ganz am Ende.
Zum Testen Ihres Codes für die Arbeitsblätter können Sie die Datei AB/Testing.hs verwenden und entsprechende import-Befehle hinzufügen. Dadurch kann vermieden werden, die import-Befehle in den Vorlagen für die Lösungen zu modifizieren.
Ein Modul entspricht einer hs-Datei. Der Modulname kann aus mehreren Teilen bestehen, welche durch . getrennt sind, z.B. MyProject.ModuleSet1.ModuleName. GHC würde dieses Modul standardmäßig in der Datei MyProject/ModuleSet1/ModuleName.hs erwarten, wobei dieser Pfad relativ zur hs-Datei ist, welche interpretiert bzw. kompiliert werden soll.
Ein Modul exportiert Funktionen, Typen, Konstruktoren und Typklassen. Wenn nichts spezifiziert ist, werden alle in diesem Modul definierten Entitäten exportiert. Alternativ kann man eine explizite Exportliste angeben, die benennt, welche Entitäten exportiert werden sollen. Alle Entitäten, welche nicht in dieser Liste enthalten sind, können nicht von außerhalb des Moduls benutzt werden (privat). Die module-Zeile sollte immer ganz am Anfang der hs-Datei stehen. Die zweite Zeile würde den Typen MyType mit Konstruktoren ConsA und ConsB und die Funktionen fun1 und fun2 exportieren.
module MyModules.XyZ where module MyModules.XyZ (MyType(ConsA,ConsB), fun1, fun2) where
Zum Importieren von Modulen wird der Befehl import genutzt. Falls keine Importliste angegeben wird, werden alle Entitäten, welche das angegebene Modul exportiert, importiert. Die zweite Zeile würde nur den Datentypen MyType ohne Konstruktoren und die Funktion fun2 importieren.
import MyModules.XyZ import MyModules.XyZ (MyType,fun2)
MyModules.XyZ.fun2. Um dies zu verkürzen, können Aliase für die Module vergeben werden, z.B. import MyModules.XyZ as Xy. Dann kann die Funktion mit Xy.fun2 referenziert werden. Weitere Optionen für das Importieren stehen im Haskell-Wiki.
Für die Abgabe eines Arbeitsblatts ABi schicken Sie bitte alle dazugehörigen Dateien ABi_j.hs und alle Ordner ABi_j als zip-Archiv per E-Mail mit dem Betreff "Abgabe ABi" an sysprog@thi.uni-hannover.de. Die zip-Datei soll nur hs- und sp-Dateien enthalten! Falls es für eine Datei ABi_j.hs keinen gleichnamigen Ordner gibt, heißt dies, dass Sie auch keine sp-Programme verwenden dürfen.
Bevor die Dateien ABi_j.hs getestet werden, werden sie zuerst mit spc kompiliert (sollten keine sp-Programme enthalten sein, dann verändert sich nichts). Anschließend durchläuft Ihre Abgabe eine Reihe von Testfällen. Falls alle Tests erfolgreich sind, wird Ihnen dies mitgeteilt und es erfolgt anschließend eine mündliche Abnahme mit allen Gruppenmitgliedern per Videochat. Alle Gruppenmitglieder müssen alle Fragen bezüglich des Codes beantworten können. Nach erfolgreicher mündlicher Abnahme gilt ein Arbeitsblatt als bestanden.
Wenn beim Testen oder bei der Abnahme ein Fehler in der Abgabe festgestellt wird, dann gilt die Abgabe als Fehlversuch (siehe dazu die Datei regelung.pdf im StudIP). Falls alle Testfälle nicht innerhalb eines großzügigen Zeitlimits durchlaufen, gilt dies ebenfalls als Fehlversuch.