Programmieren in Haskell

Syntax und Semantik von Haskell

Programmieren in Haskell 1

Was wir heute (und nächstes mal) machen

• Datentypdefinitionen

• Wertdefinitionen, Variablenbindungen

• Musterbindungen

• Funktionsbindungen

• Bewachte Gleichungen

• Lokale Definitionen mit where und let

• Gültigkeitsbereiche

• Fallunterscheidungen

• Syntaktischer Zucker / Kernsprache

Programmieren in Haskell 2

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

Programmieren in Haskell 3

Wahrheitswerte

data Bool = False | True -- vordefiniert

Programmieren in Haskell 4

Ganze Zahlen

data Ganz = Zero |

Succ Ganz

Zero, Succ Zero, Succ (Succ Zero), . . .

Eingebaute Datentypen: Int und Integer

Programmieren in Haskell 5

Tupeltypen

data Pair a b = Pair a b

data Triple a b c = Triple a b c

Eingebaute Datentypen: (a,b), (a,b,c)

Programmieren in Haskell 6

Listen

data List a = Empty | Front a (List a)

Eingebauter Datentyp: [a]

Programmieren in Haskell 7

Allgemeine Form

data T a1 . . . am = C1 t11 . . . t1n1

| . . .

| Cr tr1 . . . trnr

T : Typkonstruktor; Ci: (Daten-)Konstruktoren; ai: Typvariablen; tij : Typen oderTypvariablen

Programmieren in Haskell 8

Selektorfunktionen auf Tupeln

fst :: (a,b) -> a -- vordefiniert

fst (a,b) = a

snd :: (a,b) -> b -- vordefiniert

snd (a,b) = b

Programmieren in Haskell 9

Selektorfunktionen auf Listen

head :: [a] -> a -- vordefiniert

head (x:xs) = x

tail :: [a] -> [a] -- vordefiniert

tail (x:xs) = xs

Programmieren in Haskell 10

Selektorfunktionen auf Musik

ton :: Musik -> Int

ton (Note ton dauer) = ton

dauer :: Musik -> Rational

dauer (Note ton dauer) = dauer

dauer (Pause dauer) = dauer

Programmieren in Haskell 11

Typsynonyme

type GanzeZahl = Int

type Bruch = Rational

type Ton = GanzeZahl

type Dauer = Bruch

Programmieren in Haskell 12

Nutzen und Gefahren von Typsynonymen

type OrdList a = [a]

sort :: [a] -> OrdList a

sort xs = xs

Typ ok? Ja

Ergebnis geordnete Liste? Nein (jedenfalls nicht im allgemeinen)

Programmieren in Haskell 13

Wertdefinitionen, Variablenbindungen

theFinalAnswer :: Integer

theFinalAnswer = 42

aShortList :: [Integer]

aShortList = [1,2,3]

helloWorld :: String

helloWorld = "Hello World"

monotonie :: Musik

monotonie = c’ (1/1) :*: monotonie

Programmieren in Haskell 14

Funktionsbindungen

length :: [a] -> Int -- vordefiniert

length [] = 0

length (a:as) = 1 + length as

Programmieren in Haskell 15

Allgemeiner Fall

f p11 . . . p1n = e1

. . . = . . .

f pk1 . . . pkn = ek

pij : Muster, ei: Ausdrücke

Programmieren in Haskell 16

Bewachte Gleichungen

member :: (Ord a) => a -> OrdList a -> Bool

member a [] = False

member a (b:bs) = a >= b && (a == b || member a bs)

member a [] = False

member a (b:bs) = if a < b then False else if a == b then True else member a bs

member a [] = False

member a (b:bs)

| a < b = False

| a == b = True

| a > b = member a bs

Programmieren in Haskell 17

Lokale Definitionen mit where

sumSquares :: Int -> Int -> Int

sumSquares x y = sqX + sqY where

sqX = x * x

sqY = y * y

Programmieren in Haskell 18

Lokale Definitionen mit let

sumSquares :: Int -> Int -> Int

sumSquares x y = let sqX = x * x

sqY = y * y

in sqX + sqY

Programmieren in Haskell 19

Abseitsregel

• Das erste Zeichen der Definition unmittelbar nach dem where bestimmt dieEinrücktiefe des neu eröffneten Definitionsblocks.

• Zeilen, die weiter als bis zu dieser Position eingerückt sind, gelten alsFortsetzungen einer begonnenen lokalen Definition.

• Zeilen auf gleicher Einrücktiefe beginnen eine neue Definition im lokalen Block.

• Die erste geringer eingerückte Zeile beendet den lokalen Block.

Programmieren in Haskell 20

Beispiel für Abseitsregel

calc x y = calc1 x +

calc2 y

where

calc1 x = squares x

where

squares x = x * x

calc2 x = x * x * x

Programmieren in Haskell 21

Fallunterscheidungen

length :: [a] -> Int -- vordefiniert

length [] = 0

length (a:as) = 1 + length as

length’ :: [a] -> Int

length’ as = case as of

[] -> 0

a:as’ -> 1 + length’ as’

last’ :: [a] -> a

last’ as = case reverse as of

a:as’ -> a

Programmieren in Haskell 22

Funktionsausdrücke

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 Abkürzung für \p1 -> \p2 -> e

Programmieren in Haskell 23

Gestaffelte Funktionen

add :: Integer -> Integer -> Integer

add m n = m + n

add’ :: Integer -> (Integer -> Integer)

add’ = \m -> \n -> m + n

Programmieren in Haskell 24

note :: Int -> Int -> Dauer -> Musik

note oct h d = Note (12 * oct + h) d

note Eine Note in einer beliebigen Oktave und von beliebiger Höhe und Dauer.

note 2 Eine Note in der dritten Oktave und von beliebiger Höhe und Dauer.

note 2 ef Die Note f in der dritten Oktave und von beliebiger Dauer.

note 2 ef (1/4) ergibt Note 29 (1/4).

Programmieren in Haskell 25

Syntaktischer Zucker / Kernsprache

• Mustergleichungen / case-Ausdrücke

length [] = 0

length (x:xs) = 1 + length xs

length’ xs = case xs of

[] -> 0

(x:xs) -> 1 + length’ xs

• Funktionsdefinitionen / Funktions-Ausdrücke

add m n = m + n

add’ = \m -> \n -> m + n

Programmieren in Haskell 26

• where-Klauseln / let-Ausdrücke

double n = add0 (dup n) where

dup a = (a,a)

double n = let dup a = (a,a) in add0 (dup n)

Programmieren in Haskell 27

Auswertung von Fallunterscheidungen

case C e1...ek of {...; C x1...xk -> e;...} (case-Regel)

⇒ e[x1/e1, . . . , xn/en]

Programmieren in Haskell 28

abs :: (Ord a, Num a) => a -> a

abs n = case n >= 0 of

True -> n

False -> -n

encode :: (Num a) => Maybe a -> a

encode x = case x of

Nothing -> -1

Just 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)

Programmieren in Haskell 29

Auswertung von Funktionsanwendungen

(\x -> e) a⇒ e[x/a] (β-Regel) (1)

Programmieren in Haskell 30

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)

Programmieren in Haskell 31

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]

Programmieren in Haskell 32

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)

Programmieren in Haskell 33