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)

Links vom Gleichheitszeichen stehen Funktionsname und Parameter. Rechts steht der Ausdruck, der das Ergebnis berechnet.

Pattern Matching – Fälle durch Muster unterscheiden

Beim Pattern Matching werden verschiedene Eingabemuster durch mehrere Definitionszeilen beschrieben. Die erste passende Zeile 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.

Ein anderes Datenmodell: 0 und 1

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

Der Unterstrich _ steht als eine Art Platzhalter für einen Wert. Dieser kann einen beliebigen Wert annehmen (typgerecht!); der konkrete Wert wird an dieser Stelle im Pattern Matching nicht weiter verwendet.

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.

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 erneut Pattern Matching: Das Tupel wird 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.

Einige eingebaute Listenfunktionen

Der Operator : heißt Cons-Operator und setzt ein Element vor eine Liste. Der Operator ++ verbindet zwei Listen.

Die Schreibweise (x:xs)

(x:xs) beschreibt eine nichtleere Liste: x ist das erste Element, xs die Restliste. Der Doppelpunkt : ist dabei der Cons-Operator.

kopf (x:xs) = x
rest (x:xs) = xs

Diese Form wird später für rekursive Listenfunktionen besonders wichtig. Die Hilfe erinnert hier bewusst nur an die Schreibweise und den Fachbegriff; sie ersetzt nicht die ausführliche Behandlung im Unterricht.

Grundform

[ ausdruck | variable <- quelle, bedingung ]

Beispiel: alle durch 3 teilbaren Zahlen von 1 bis 20.

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

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

Die Form der Listenelemente bestimmen

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

Der Ausdruck links vom senkrechten Strich bestimmt, was in der Ergebnisliste landet. Hier wird aus jedem passenden x ein Tupel aus Zahl und Quadrat.

Mehrere Generatoren

[(x,y) | x <- [0,1], y <- [0,1]]

Ergebnis:

[(0,0),(0,1),(1,0),(1,1)]

Damit lassen sich sehr bequem alle möglichen Belegungen zweier logischer Eingänge erzeugen.

Von der logischen Funktion zur Wahrheitstabelle

Jetzt greifen bekannte Logik und Listengenerator ineinander.

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]]

wahrheitNand erzeugt die Eingangsbelegungen und berechnet für jede Belegung den Ausgang der Haskell-Funktion.

Mehrere Bedingungen

[(i,j,i*j) |
  i <- [1..100],
  j <- [3,6..99],
  mod (i+j) 7 == 0]

Mehrere Bedingungen werden durch Kommas getrennt. Nur Kombinationen, die alle Bedingungen erfüllen, gelangen in die Ergebnisliste.

Rekursionsanker und Rekursionsschritt

Eine rekursive Definition braucht zwei Dinge:

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

Eine rekursive Auswertung nachvollziehen

summe 4
= 4 + summe 3
= 4 + 3 + summe 2
= 4 + 3 + 2 + summe 1
= 4 + 3 + 2 + 1 + summe 0
= 4 + 3 + 2 + 1 + 0
= 10

Der Rekursionsanker beendet die Kette. Danach können die noch offenen Ausdrücke vollständig ausgewertet werden.

Ein weiteres Muster: ggT

ggt :: Int -> Int -> Int
ggt a 0 = a
ggt a b
  | a > b     = ggt (a-b) b
  | otherwise = ggt a (b-a)

Hier treffen Pattern Matching, Guards und Rekursion zusammen. Entscheidend ist, dass sich die Eingaben in Richtung des Abbruchfalls verändern.

Vertiefung: Akkumulator

Manche rekursiven Funktionen führen ein Zwischenergebnis als zusätzlichen Parameter mit. Diesen Parameter nennt man Akkumulator. Für viele grundlegende Aufgaben ist das zunächst nicht nötig.

summeAkk n = hilfe n 0

hilfe 0 akk = akk
hilfe n akk = hilfe (n-1) (akk+n)

Die zwei Listenfälle

Kopf und Rest selbst definieren

kopf :: [a] -> a
kopf (x:xs) = x

rest :: [a] -> [a]
rest []     = []
rest (x:xs) = xs

Das Muster (x:xs) zerlegt die Liste. Es ist kein Tupel.

Länge einer Liste rekursiv bestimmen

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

Beim Rekursionsschritt wird nicht die ursprüngliche Liste, sondern nur noch die Restliste xs verarbeitet.

Ein Element suchen

istEnthalten :: Eq a => a -> [a] -> Bool
istEnthalten y [] = False
istEnthalten y (x:xs)
  | y == x    = True
  | otherwise = istEnthalten y xs

Hier greifen Listenmuster, Guards und Rekursion ineinander. Dieses Muster ist für viele weitere Listenalgorithmen wichtig.

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