Haskell am WvS – Hilfe

Ausdrücke direkt testen

13 + 42
2 ^ 10
(+) 16 26
"Ha" ++ "skell"
7 > 4
True && False

GHCi wertet einen eingegebenen Ausdruck aus und zeigt das Ergebnis an.

Wichtige GHCi-Befehle

Fehlermeldungen lesen

Fehlermeldungen sind Teil der Arbeit. Lesen Sie zuerst die genannte Datei und Zeile, danach die eigentliche Meldung. Prüfen Sie besonders Schreibweise, Klammern, Einrückung und Typen.

Einfacher Aufbau

square :: Int -> Int
square x = x ^ 2

doppelt :: Int -> Int
doppelt x = 2 * x

Typangabe und Funktionsdefinition stehen normalerweise direkt beieinander.

Kommentare

-- einzeiliger Kommentar
quadrat x = x * x  -- Kommentar am Zeilenende

Kommentare werden nicht ausgeführt. Nutzen Sie sie sparsam für Hinweise, die der Code selbst nicht schon deutlich macht.

Der Arbeitszyklus

Eine Funktion definieren

add5 :: Int -> Int
add5 x = x + 5

bmi :: Float -> Float -> Float
bmi gewicht groesse = gewicht / (groesse * groesse)

Bei einer einfachen Funktionsdefinition stehen links vom Gleichheitszeichen der Funktionsname und die Parameterbezeichner. Rechts steht der Ausdruck, der das Ergebnis berechnet. Beim Pattern Matching können an der Stelle der Parameterbezeichner auch konkretere Muster stehen.

Pattern Matching – Muster vergleichen

Pattern Matching ist der Mustervergleich der Argumente einer Funktion mit den links vom Gleichheitszeichen angegebenen Mustern. Die Funktionsgleichungen werden von oben nach unten geprüft; die erste passende Gleichung wird verwendet.

und :: Bool -> Bool -> Bool
und True  True  = True
und True  False = False
und False True  = False
und False False = False

Die vier Zeilen entsprechen direkt den vier möglichen Belegungen einer Wahrheitstabelle mit zwei Eingängen.

Bezeichner und Platzhalter im Muster

nand :: Int -> Int -> Int
nand 1 1 = 0
nand _ _ = 1

zweite (_,b) = b

Ein Bezeichner in einem Muster bindet den dazu passenden Wert. Der Unterstrich _ ist ein Platzhalter: Er passt auf einen typgerechten Wert, bindet ihn aber nicht an einen Namen.

Guards – Fälle durch Bedingungen unterscheiden

Guards stehen hinter einem senkrechten Strich. Die Bedingungen werden von oben nach unten geprüft.

betrag :: Int -> Int
betrag x
  | x >= 0    = x
  | otherwise = -x

otherwise ist der Auffangfall, wenn keine vorherige Bedingung erfüllt wurde. Auch vor otherwise muss der Guard-Strich | stehen.

Funktionen miteinander verwenden

nicht3 :: Int -> Int
nicht3 0 = 1
nicht3 1 = 0

und3 a b = nand (nand a b) (nand a b)

Eine Funktion kann andere bereits definierte Funktionen aufrufen. So lassen sich komplexere Berechnungen aus kleinen Bausteinen zusammensetzen.

Kurz: lokale Hilfsdefinition mit where

where kann eine kleine Hilfsdefinition direkt an eine Funktion binden. Für unseren Lernweg ist das kein eigener Schwerpunkt; let und case werden hier bewusst nicht eingeführt.

summeHoch3 x y = summe * summe * summe  -- berechnet (x + y)^3
  where
    summe = x + y

Häufige Typen

Funktions-Typen lesen

square :: Int -> Int
max2   :: Int -> Int -> Int
nand   :: Int -> Int -> Int

Bei max2 und nand stehen zwei Eingabetypen vor dem Ergebnistyp. Der Ergebnistyp steht ganz rechts. Für den Einstieg genügt diese Lesart: zwei Eingaben hinein, ein Ergebnis heraus.

Typen in GHCi untersuchen

:t True
:t "Hallo"
:t [1,2,3]
:t (2,'a')

Mit :t können Sie Vermutungen über Typen direkt überprüfen.

Tupel

(2,3)
('a',2)
("Ada", 1815, True)

Tupel stehen in runden Klammern. Ihre Komponenten dürfen unterschiedliche Typen haben.

fst (2,3)       -- 2
snd (2,3)       -- 3

dritte (a,b,c) = c

Das letzte Beispiel zeigt Pattern Matching: Das Tupel wird durch das Muster (a,b,c) direkt in seine Bestandteile zerlegt.

Listen

[2,4,3,4]
[1..5]
[1,3..11]
['a'..'z']
[]

Alle Elemente einer Liste müssen denselben Typ besitzen. Doppelte Elemente sind erlaubt; auch die leere Liste [] ist eine Liste. Schreibweisen wie [1..5] oder [1,3..11] erzeugen Werte mit gleichmäßigen Abständen.

Einige eingebaute Listenfunktionen

++ verbindet zwei Listen. Die Zerlegung einer Liste in erstes Element und Restliste sowie der Cons-Operator : folgen nach den Listengeneratoren im nächsten Lernschritt.

Grundform ohne Filter

[ Ergebnisausdruck | Muster <- Ausgangsliste ]

Der Teil Muster <- Ausgangsliste heißt Generator. Links von <- steht formal ein Pattern, also ein Muster. Im einfachsten Fall ist dieses Muster nur ein Bezeichner wie x.

[x | x <- [1..5]]

x nimmt nacheinander die Werte aus der Ausgangsliste an. Das Ergebnis ist hier wieder [1,2,3,4,5].

Den Ergebnisausdruck verändern

[x*x | x <- [1..5]]
[(x, x*x) | x <- [1..5]]

Der Ausdruck links vom senkrechten Strich bestimmt die Form der Elemente in der Ergebnisliste. Das Muster im Generator bleibt dabei x.

Werte mit einer Bedingung filtern

[ Ergebnisausdruck | Muster <- Ausgangsliste, Bedingung ]

Nur Werte, für die die Bedingung True ergibt, gelangen in die Ergebnisliste.

[x | x <- [1..20], mod x 3 == 0]

Ergebnis: [3,6,9,12,15,18].

Mehrere Bedingungen

[x | x <- [1..100], div x 5 > 4, mod x 7 == 0]

Mehrere Filter werden durch Kommas getrennt. Ein Wert wird nur übernommen, wenn alle Bedingungen erfüllt sind; die Kommas wirken hier also wie eine logische UND-Verknüpfung der Bedingungen.

Mehrere Generatoren

[(x,y) | x <- [1..3], y <- ['a'..'c']]

Bei mehreren Generatoren kann man sich die Auswertung ähnlich wie geschachtelte Durchläufe vorstellen: Der erste Generator bildet den äußeren, der zweite den inneren Durchlauf.

x <- [1..3]       -- äußerer Generator
y <- ['a'..'c']   -- innerer Generator

Transfer: Eingaberäume systematisch erzeugen

nand :: Int -> Int -> Int
nand 1 1 = 0
nand _ _ = 1

belegung2 = [(a,b) | a <- [0,1], b <- [0,1]]

wahrheitNand =
  [(a,b,nand a b) | a <- [0,1], b <- [0,1]]

Der Cons-Operator :

Rechts vom Gleichheitszeichen setzt : ein Element vor eine Liste.

1 : [2,3]      -- [1,2,3]
'a' : "bc"     -- "abc"

Links vom Gleichheitszeichen kann dieselbe Schreibweise als Muster auftreten:

kopf (x:xs) = x

Das Muster (x:xs) passt auf eine nichtleere Liste. x bindet das erste Element, xs die Restliste. Es ist kein Tupel.

Rekursionsanker und Rekursionsschritt

Eine rekursive Definition braucht mindestens einen Fall ohne weiteren Selbstaufruf und einen Fall, in dem die Funktion sich mit einer veränderten Eingabe erneut aufruft. Das folgende Beispiel ist für n >= 0 gedacht.

summeBis :: Int -> Int
summeBis 0 = 0                         -- Rekursionsanker
summeBis n = n + summeBis (n-1)       -- Rekursionsschritt

Eine rekursive Auswertung nachvollziehen

summeBis 4
= 4 + summeBis 3
= 4 + (3 + summeBis 2)
= 4 + (3 + (2 + summeBis 1))
= 4 + (3 + (2 + (1 + summeBis 0)))
= 4 + (3 + (2 + (1 + 0)))
= 10

Der Rekursionsanker beendet die Kette der Selbstaufrufe. Erst danach sind alle noch offenen Teilausdrücke vollständig bestimmbar.

Die zwei grundlegenden Listenmuster

Wird das erste Element nicht benötigt, kann der Platzhalter verwendet werden: (_:xs).

Länge einer Liste rekursiv bestimmen

laenge :: [a] -> Int
laenge []     = 0
laenge (_:xs) = 1 + laenge xs

Der Wert des ersten Elements ist für die Länge unwichtig. Deshalb steht dort _. Im Rekursionsschritt wird nur noch die Restliste xs verarbeitet.

Elemente verarbeiten

summe []     = 0
summe (x:xs) = x + summe xs

produkt []     = 1
produkt (x:xs) = x * produkt xs

Die Struktur ist gleich; nur Ankerwert und Verknüpfung unterscheiden sich.

Ein Element suchen

istEnthalten _ [] = False
istEnthalten y (x:xs)
  | y == x    = True
  | otherwise = istEnthalten y xs

Hier greifen Listenmuster, Guards und Rekursion ineinander.

Die Spezifikation entscheidet über die Fälle

Nicht jede Funktion muss für jede denkbare Eingabe definiert sein. Wenn eine Aufgabe beispielsweise ausdrücklich eine nichtleere Liste voraussetzt, muss nicht automatisch ein zusätzlicher Fall für [] mit einer Fehlermeldung erfunden werden. Entscheidend ist die angegebene Spezifikation.

Ein Element in eine sortierte Liste einfügen

einfuegen :: Ord a => a -> [a] -> [a]
einfuegen y [] = [y]
einfuegen y (x:xs)
  | y <= x    = y : x : xs
  | otherwise = x : einfuegen y xs

Ist die Liste leer, besteht das Ergebnis nur aus y. Sonst wird entschieden, ob y vor das erste Element gehört oder in der Restliste weitergesucht werden muss.

Insertion Sort

isort :: Ord a => [a] -> [a]
isort []     = []
isort (x:xs) = einfuegen x (isort xs)

Die Restliste wird zuerst rekursiv sortiert. Danach wird x mit einfuegen an die richtige Stelle gesetzt.

Quicksort mit Listengeneratoren

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
  quicksort [y | y <- xs, y <= x]
  ++ [x] ++
  quicksort [y | y <- xs, y > x]

Das erste Element x dient als Trennelement. Zwei Listengeneratoren teilen die Restliste in kleinere beziehungsweise gleich große und größere Elemente. Beide Teillisten werden rekursiv sortiert.

Algorithmen vergleichen

1. Moduldatei und Modulname

Der Modulname beginnt mit einem Großbuchstaben. Bei einem benannten Modul muss der Dateiname zum Modulnamen passen.

Darunter stehen die bereits erarbeiteten Definitionen von ggT und kgV. Die Namen in der Klammer hinter module bilden die Exportschnittstelle. Nur diese Namen werden nach außen angeboten.

2. Modul in einer anderen Datei verwenden

-- andere Haskell-Datei im selben Ordner
import GgtKgvModul

beispiel1 = ggT 84 30
beispiel2 = kgV 12 18

Die Moduldatei und die verwendende Datei liegen für diesen einfachen Fall im selben Ordner. Geladen wird anschließend die verwendende Datei; der Import zieht das Modul hinzu.

3. Nur ausgewählte Funktionen importieren

import GgtKgvModul (ggT)

So wird aus dem Modul nur der angegebene Name in der eigenen Datei verfügbar.

4. Lokales Modul oder zentral installiertes Modul?

import Zeitmessung

1. Modul in GHCi einbinden

ghci> :l meineDatei.hs
ghci> import Zeitmessung
ghci> Zeitmessung.hilfe

Mehr ist nicht zu installieren. Das Modul ist im Haskell-Labor zentral verfügbar. Zeitmessung.hilfe zeigt jederzeit die Kurz-API; für Messungen ist die direkte Nutzung im GHCi meist am einfachsten.

2. Die acht Befehle

3. Beispiele

Ohne Parameter: ein Wert

ghci> laufzeit0 porto1

Eine Definition wie porto1 = [...] ist in Haskell keine Funktion mit null Argumenten, sondern ein Wert. Dafür ist laufzeit0 gedacht.

Ein Argument

laufzeit porto2 222
laufzeit fib 35
laufzeit reverse [1..100000]
laufzeit listenmaximum [1..100000]

Zwei Argumente

laufzeit2 hlaenge "Informatik" 0
laufzeit2 istEnthalten 99999 [1..100000]

Drei Argumente

laufzeit3 hfib 35 1 1

Tupel

Ein Tupel ist für die Zeitmessung ein Argument:

laufzeit quadratsumme (3,4)

4. GHCi ist nicht dasselbe wie eine .hs-Datei

Im GHCi dürfen Ausdrücke direkt ausgeführt werden:

ghci> laufzeit porto2 222

In einer .hs-Datei darf derselbe Ausdruck nicht allein auf oberster Ebene stehen. Dort stehen Definitionen bzw. Deklarationen:

import Zeitmessung

testPorto2 :: IO ()
testPorto2 = laufzeit porto2 222

Nach dem Laden kann dann im GHCi testPorto2 aufgerufen werden.

5. Funktionen höherer Ordnung

Eine Funktion als Argument wird am besten vorher teilweise angewendet:

laufzeit (map quadrat) [1..100000]
laufzeit (filter even) [1..100000]

So erhält laufzeit wieder eine normale Funktion mit einem Datenargument.

6. Ausgabe verstehen

ghci> laufzeit fib 40
Berechnung läuft ....
Laufzeit: 4.238741 s

Jeder Punkt ist nur ein Lebenszeichen ungefähr pro Sekunde. Er ist kein prozentualer Fortschritt.

ghci> getLimit
Zeitlimit: 10 Sekunden

ghci> laufzeit fib 50
Berechnung läuft ..........
Zeitlimit von 10 Sekunden überschritten.
Berechnung wurde abgebrochen. GHCi läuft weiter.
Tipp: kleinere Eingabe verwenden oder mit setLimit n das Zeitlimit ändern.
Hilfe: Zeitmessung.hilfe

Eine Zeitüberschreitung ist kein Bedienfehler. Bei setLimit 0 erscheint dagegen ein Hinweis auf Zeitmessung.hilfe. Die angezeigte Laufzeit erfasst weiterhin nur die Funktionsauswertung, nicht die Vorbereitung der Eingabe.

7. Schutz vor zu aufwendigen Berechnungen

Standard: 10 Sekunden. Die Zeitbegrenzung beginnt vor der vollständigen Auswertung der Eingabe und gilt für Vorbereitung und Berechnung zusammen. Mit setLimit 20 lässt sich das Limit für die aktuelle GHCi-Sitzung anpassen.

Ein zusätzlicher interner Allokationsschutz begrenzt die insgesamt zugeteilte Speichermenge während eines Messaufrufs (anfänglich 512 MiB). Er misst nicht den tatsächlich belegten Arbeitsspeicher und ist keine Garantie gegen einen Systemabbruch.

ghci> laufzeit reverse [1..100000000]
Berechnung läuft ...
Sicherheitslimit für Rechen-/Speicheraufwand erreicht.
Berechnung wurde abgebrochen. GHCi läuft weiter.

Je nachdem, welcher Grenzwert zuerst erreicht wird, kann stattdessen die Meldung „Zeitlimit von 10 Sekunden überschritten“ erscheinen. Im Normalfall bleibt GHCi erhalten. Falls Linux GHCi trotzdem beendet, startet der Watchdog GHCi neu; gespeicherte .hs-Dateien sind davon nicht betroffen.

8. Messwerte sinnvoll vergleichen

• Dieselbe Funktion mit mehreren Eingabegrößen messen.
• Beim Vergleich verschiedener Algorithmen möglichst dieselben Eingaben verwenden.
• Eine Messung bei Bedarf wiederholen; kleine Zeiten schwanken.
• Keine unendlichen Listen verwenden: der Schutz soll hängenbleibende Berechnungen abbrechen, ersetzt aber kein sinnvolles Eingabedesign.