Programmieren in HaskellSyntax und Semantik von Haskell
Peter Steffen
Universitat BielefeldTechnische Fakultat
13.11.2009
1 Programmieren in Haskell
Was wir heute machen
Datentypdefinitionen
Wertdefinitionen, Variablenbindungen
Musterbindungen
Funktionsbindungen
Bewachte Gleichungen
Lokale Definitionen mit where und let
Gultigkeitsbereiche
Fallunterscheidungen
Syntaktischer Zucker / Kernsprache
2 Programmieren in Haskell
Datentypen, Datentypdefinitionen
data Instrument = Oboe| HonkyTonkPiano| Cello| VoiceAahs
data Musik = Note Ton Dauer| Pause Dauer| Musik :*: Musik| Musik :+: Musik| Instr Instrument Musik| Tempo GanzeZahl Musik
3 Programmieren in Haskell
Wahrheitswerte
data Bool = False | True -- vordefiniert
4 Programmieren in Haskell
Ganze Zahlen
data Ganz = Zero |Succ Ganz
Zero, Succ Zero, Succ (Succ Zero), . . .
Eingebaute Datentypen: Int und Integer
5 Programmieren in Haskell
Tupeltypen
data Pair a b = Pair a bdata Triple a b c = Triple a b c
Eingebaute Datentypen: (a,b), (a,b,c)
6 Programmieren in Haskell
Listen
data List a = Empty | Front a (List a)
Eingebauter Datentyp: [a]
7 Programmieren in Haskell
Allgemeine Form
data T a1 . . . am = C1 t11 . . . t1n1
| . . .
| Cr tr1 . . . trnr
T : Typkonstruktor; Ci : (Daten-)Konstruktoren; ai : Typvariablen; tij : Typenoder Typvariablen
8 Programmieren in Haskell
Allgemeine Form
data T a1 . . . am = C1 t11 . . . t1n1
| . . .
| Cr tr1 . . . trnr
T : Typkonstruktor; Ci : (Daten-)Konstruktoren; ai : Typvariablen; tij : Typenoder Typvariablen
8 Programmieren in Haskell
Selektorfunktionen auf Tupeln
fst :: (a,b) -> a -- vordefiniertfst (a,b) = a
snd :: (a,b) -> b -- vordefiniertsnd (a,b) = b
9 Programmieren in Haskell
Selektorfunktionen auf Listen
head :: [a] -> a -- vordefinierthead (x:xs) = x
tail :: [a] -> [a] -- vordefinierttail (x:xs) = xs
10 Programmieren in Haskell
Selektorfunktionen auf Musik
ton :: Musik -> Intton (Note ton dauer) = ton
dauer :: Musik -> Rationaldauer (Note ton dauer) = dauerdauer (Pause dauer) = dauer
11 Programmieren in Haskell
Typsynonyme
type GanzeZahl = Inttype Bruch = Rational
type Ton = GanzeZahltype Dauer = Bruch
12 Programmieren in Haskell
Nutzen und Gefahren von Typsynonymen
type OrdList a = [a]sort :: [a] -> OrdList a
sort xs = xs
Typ ok? JaErgebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)
13 Programmieren in Haskell
Nutzen und Gefahren von Typsynonymen
type OrdList a = [a]sort :: [a] -> OrdList a
sort xs = xs
Typ ok? JaErgebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)
13 Programmieren in Haskell
Nutzen und Gefahren von Typsynonymen
type OrdList a = [a]sort :: [a] -> OrdList a
sort xs = xs
Typ ok? JaErgebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)
13 Programmieren in Haskell
Nutzen und Gefahren von Typsynonymen
type OrdList a = [a]sort :: [a] -> OrdList a
sort xs = xs
Typ ok? JaErgebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)
13 Programmieren in Haskell
Nutzen und Gefahren von Typsynonymen
type OrdList a = [a]sort :: [a] -> OrdList a
sort xs = xs
Typ ok? JaErgebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)
13 Programmieren in Haskell
Wertdefinitionen, Variablenbindungen
aShortList :: [Integer]aShortList = [1,2,3]
helloWorld :: StringhelloWorld = "Hello World"
monotonie :: Musikmonotonie = c’ (1/1) :*: monotonie
14 Programmieren in Haskell
Funktionsbindungen
length :: [a] -> Int -- vordefiniertlength [] = 0length (a:as) = 1 + length as
15 Programmieren in Haskell
Allgemeiner Fall
f p11 . . . p1n = e1
. . . = . . .
f pk1 . . . pkn = ek
pij : Muster, ei : Ausdrucke
16 Programmieren in Haskell
Bewachte Gleichungen
member :: (Ord a) => a -> OrdList a -> Boolmember a [] = Falsemember a (b:bs) = a >= b && (a == b || member a bs)
member a [] = Falsemember a (b:bs) = if a < b then False else
if a == b then True else member a bs
member a [] = Falsemember a (b:bs)
| a < b = False| a == b = True| a > b = member a bs
17 Programmieren in Haskell
Lokale Definitionen mit where
sumSquares :: Int -> Int -> IntsumSquares x y = sqX + sqY wheresqX = x * xsqY = y * y
18 Programmieren in Haskell
Lokale Definitionen mit let
sumSquares :: Int -> Int -> IntsumSquares x y = let sqX = x * x
sqY = y * yin sqX + sqY
19 Programmieren in Haskell
Abseitsregel
Das erste Zeichen der Definition unmittelbar nach dem wherebestimmt die Einrucktiefe des neu eroffneten Definitionsblocks.
Zeilen, die weiter als bis zu dieser Position eingeruckt sind, gelten alsFortsetzungen einer begonnenen lokalen Definition.
Zeilen auf gleicher Einrucktiefe beginnen eine neue Definition imlokalen Block.
Die erste geringer eingeruckte Zeile beendet den lokalen Block.
20 Programmieren in Haskell
Beispiel fur Abseitsregel
calc x y = calc1 x +calc2 y
wherecalc1 x = squares xwheresquares x = x * x
calc2 x = x * x * x
21 Programmieren in Haskell
Fallunterscheidungen
length :: [a] -> Int -- vordefiniertlength [] = 0length (a:as) = 1 + length as
length’ :: [a] -> Intlength’ as = case as of
[] -> 0a:as’ -> 1 + length’ as’
last’ :: [a] -> alast’ as = case reverse as of
a:as’ -> a
22 Programmieren in Haskell
Funktionsausdrucke
Ist n + 1 ein Wert oder eine Funktion?Als Funktion:
f n = n + 1
\n -> n + 1
Allgemeine Form eines Funktionsausdrucks:
\p1 . . . pn -> e .
\p1 p2 -> e als Abkurzung fur \p1 -> \p2 -> e
23 Programmieren in Haskell
Gestaffelte Funktionen
add :: Integer -> Integer -> Integeradd m n = m + n
add’ :: Integer -> (Integer -> Integer)add’ = \m -> \n -> m + n
24 Programmieren in Haskell
Gestaffelte Funktionen
note :: Int -> Int -> Dauer -> Musiknote oct h d = Note (12 * oct + h) d
note Eine Note in einer beliebigen Oktave und von beliebigerHohe und Dauer.
note 2 Eine Note in der dritten Oktave und von beliebiger Hohe undDauer.
note 2 ef Die Note f in der dritten Oktave und von beliebiger Dauer.
note 2 ef (1/4) ergibt Note 29 (1/4).
25 Programmieren in Haskell
Syntaktischer Zucker / Kernsprache
Mustergleichungen / case-Ausdrucke
length [] = 0length (x:xs) = 1 + length xs
length’ xs = case xs of[] -> 0(x:xs) -> 1 + length’ xs
Funktionsdefinitionen / Funktions-Ausdrucke
add m n = m + n
add’ = \m -> \n -> m + n
26 Programmieren in Haskell
where-Klauseln / let-Ausdrucke
where-Klauseln / let-Ausdrucke
double n = add0 (dup n) wheredup a = (a,a)
double n = let dup a = (a,a) in add0 (dup n)
27 Programmieren in Haskell
Auswertung von Fallunterscheidungen
case C (e1) . . . (ek)of{. . . ; C (x1) . . . (xk)− > e; . . .}(case-Regel)⇒ e[x1/e1, . . . , xn/en]
28 Programmieren in Haskell
abs :: (Ord a, Num a) => a -> aabs n = case n >= 0 of
True -> nFalse -> -n
encode :: (Num a) => Maybe a -> aencode x = case x of
Nothing -> -1Just n -> abs n
encode (Just 5)
⇒ case Just 5 of {Nothing -> -1; Just n -> abs n} (Def. encode)
⇒ abs 5 (case− Regel)
⇒ case 5 >= 0 of {True -> 5; False -> -5} (Def. abs)
⇒ case True of {True -> 5; False -> -5} (Def. >=)
⇒ 5 (case− Regel)
29 Programmieren in Haskell
Auswertung von Funktionsanwendungen
(\(x)− > (e))(a)⇒ e[x/a] (β-Regel)
30 Programmieren in Haskell
abs = \n -> case n >= 0 of {True -> n; False -> -n}encode = \x -> case x of {Nothing -> -1; Just n -> abs n}
encode (Just 5) (Def. encode)
⇒ (\x-> case x of {Nothing-> -1; Just n-> abs n}) (Just 5)
⇒ case Just 5 of {Nothing -> -1; Just n -> abs n} (β − Regel)
⇒ abs 5 (case− Regel)
⇒ (\n -> case n >= 0 of {True -> n; False -> -n}) 5 (Def. abs)
⇒ case 5 >= 0 of {True -> 5; False -> -5} (β − Regel)
⇒ case True of {True -> 5; False -> -5} (Def. (>=))
⇒ 5 (case− Regel)
31 Programmieren in Haskell
Auswertung von lokalen Definitionen
let {x1 = e1;...;xn = en} in e
⇒ e[x1/ let {x1 = e1;...;xn = en} in e1, . . . ,(let-Regel)
xn/ let {x1 = e1;...;xn = en} in en]
32 Programmieren in Haskell
rep n a = let x = a:x in take n x
rep 2 8
⇒ let x = 8:x in take 2 x (Def. rep)
⇒ take 2 (let x = 8:x in 8:x) (let− Regel)
⇒ take 2 (8:let x = 8:x in 8:x) (let− Regel)
⇒ 8:take 1 (let x = 8:x in 8:x) (Def. take)
⇒ 8:take 1 (8:let x = 8:x in 8:x) (let− Regel)
⇒ 8:8:take 0 (let x = 8:x in 8:x) (Def. take)
⇒ 8:8:[] (Def. take)
33 Programmieren in Haskell