Typen |
|
|
curried functions |
|
|
polymorphe Typen |
|
|
:type |
|
|
Programme | sind Dateien mit Funktionsdefinitionen |
Curried Functions mit zwei Argumenten kann man auch zwischen die Argumente schreiben:
x = div a b -- curried Funktionsanwendung
x = a `div` b -- zwischen die Argumente geschrieben
Operatoren kann man auch als Curried Function schreiben:
z = x + y -- mathematische Notation
z = (+) x y -- als Funktionsanwendung
:type (+) -- so kann man den Typ von Operationen bekommen
(+) :: Num a => a -> a -> a
Eine Klasse ist eine Sammlung von Typen, die überladene Operationen unterstützen. Diese Operationen heißen Methoden.
:type (+)
(+) :: Num a => a -> a -> a -- a ist ein Zahlentyp
z = 1+2 -- Int Addition
z = 1.0+2.0 -- Float Addition
Klasse | überladene Methoden |
---|---|
Eq |
|
Ord |
|
Show |
|
Read |
|
Klasse | überladene Methoden |
---|---|
Num |
|
Integral |
|
Fractional |
|
Probiert einfach mal die überladenen Methoden in ghci aus.
Beim Definieren von Funktionen sollte man immer erst den Typ notieren.
even :: Integral a => a -> Bool
even n = n `mod` 2 == 0
splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs = (take n xs, drop n xs) -- Konventionen beachtet
recip :: Fractional a => a -> a
recip n = 1/n
Eine Folge von logischen Ausdrücken heißen Guards. Sie dienen dazu, zwischen Ausdrücken desselben Typs auszuwählen.
abs :: Num a => a -> a
abs n | n >= 0 = n -- das erste Match bestimmt den Wert
| otherwise = -n -- otherwise hat den Wert True
signum :: Num a => a -> a
signum n | n < 0 = -1
| n == 0 = 0
| otherwise = 1
Man kann auch ein Wildcard-Pattern _ einsetzen. Damit kann man Funktionen noch effizienter definieren.
(&&) :: Bool -> Bool -> Bool -- die Konjunktion
True && True = True -- ohne Wildcard,
True && False = False -- in Tabellenform
False && True = False
False && False = False
(&&) :: Bool -> Bool -> Bool -- die Konjunktion
True && b = b
_ && _ = False -- mit Wildcard
Ein Tupel von Patterns ist ein Tuple-Pattern.
fst :: (a,b) -> a
fst (x,_) = x -- x ist vom Typ a
snd :: (a,b) -> b
snd (_,y) = y -- y ist vom Typ b
Eine Liste von Patterns ist ein List-Pattern.
Beispiel: "test" sei eine Funktion, die überprüft, ob eine Liste genau drei Elemente enthält, von denen das erste ein 'a' ist.
test :: [Char] -> Bool
test ['a',_,_] = True -- _ ist vom Typ Char
test _ = False -- _ ist vom Typ [Char]
Listen sind keine primitiven Typen, sondern werden mit dem :-Operator construiert.
[1,2,3] = 1:[2,3] -- 1 an die Liste [2,3] vorne angefügt
= 1:2:[3] -- ...
= 1:2:3:[] -- bis wir bei der leeren Liste sind.
head :: [a] -> a
head (x:_) = x -- das ist gut zu verstehen.
tail :: [a] -> a
tail (_:xs) = xs -- Konvention beachtet ;-)
Anstelle von Gleichungen kann man auch Lambda-Expressions verwenden. Das griechische $$ \lambda $$ wird in Haskell durch "\" dargestellt.
Lambda-Expressions sind Funktionsdefinitionen
ohne Namen.
\x -> x + x
(\x -> x+x) 2
4
Es ergibt Sinn, Lambda-Expressions zu verwenden:
const :: a -> b -> a -- die konstante Funktion:
const x _ = x -- nicht gut zu verstehen.
const :: a -> b -> a -- die konstante Funktion:
const x = \_ -> x -- gut zu verstehen.
Noch ein Beispiel: Wenn man eine Funktion nur einmal braucht, muss man nicht notwendigerweise einen Namen definieren:
odds :: Int -> [Int] -- die ersten n ungeraden Zahlen
odds n = map f [0..n-1] -- f wird explizit benannt
where f x = x*2 + 1 -- und definiert
odds :: Int -> [Int] -- f wird durch Lambda-Expression
odds n = map (\x -> x*2 + 1) [0..n-1] -- ersetzt
halve :: [a] -> ([a],[a])
die eine Liste mit einer geraden Anzahl Elemente halbiert.
> halve [1,2,3,4,5,6]
([1,2,3],[4,5,6])
third :: [a] -> a
die das dritte Element einer Liste mit mindestens drei Elementen
zurückliefert. Verwende dazu:
safetail :: [a] -> [a]
die genau wie tail arbeitet, aber bei der leeren Liste keinen Fehler
wirft. Verwende dabei die Funktionen tail und null.
Mit List Comprehensions kann man viele Funktionen auf Listen sehr einfach definieren. Wir haben in den einführenden Beispielen schon einige List-Comprehensions gesehen.
Die Notation kommt aus der Mathematik: $$ \{ x^2 | x \in \{ 1 .. 5\} \} $$ und heißt dort "Set Comprehension Notation"
[x^2 | x <- [1..5] ]
[1,4,9,16,25]
Der Ausdruck x <- [1..5]
ist
ein Generator.
Beispiele:
concat :: [[a]] -> [a] -- macht eine Liste von Listen flach
concat xss = [x | xs <- xss, x <-xs ]
firsts :: [(a,b)] -> [a] -- gibt alle ersten Elemente
firsts ps = [x | (x,_) <- ps ] -- der Paare zurück
length :: [a] -> Int -- berechnet die Länge einer Liste
length xs = sum [1 | _ <- xs ]
Guards dienen bei den Comprehensions als Filter:
teiler :: Int -> [Int]
teiler n = [x | x <- [1..n], n `mod` x == 0 ]
istprim :: Int -> Bool
istprim n = length (teiler n) == 2
primzahlenkleiner :: Int -> [Int]
primzahlenkleiner n = [x | x <- [1..n], istprim x ]
primzahlenkleiner 40
[2,3,5,7,11,13,17,19,23,29,31,37]
Cäsar Verschlüsselung per Brute-Force knacken.
Holt euch nen Kaffee, lehnt euch zurück und schaut zu.
Man braucht in funktionalen Sprachen gar keine Schleifen. Rekursionen ersetzen Schleifen prima.
Standardbeispiel für Rekursion: Die Fakultät
fac :: Int -> Int
fac n = product [1..n] -- ok, das ist keine Rekursion
fac :: Int -> Int
fac 0 = 1 -- Rekursionsanfang
fac n = n * fac (n-1) -- Rekursion
Rekursion über Listen ... Beispiele
product :: Num a => [a] -> a
product [] = 1
product (n:ns) = n * product ns
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
Insertion Sort:
-- einsortieren (insert) eines Elements in eine sortierte Liste:
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
| otherwise = y : insert x ys
isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)
Woran man wieder sehen kann, wie mächtig und natürlich Rekursion ist.
... Ich habe immer meine Probleme gehabt, die imperativen Quicksort Implementierungen zu verstehen ...
Anekdote: die Wiegereihe in einer 9. Klasse
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
where
smaller = [s | s <- xs, s <= x ]
larger = [l | l <- xs, l > x ]
vollzieht die Beispiele selbst nach und probiert einfach mal aus.
Zum Selbermachen:
http://domay.de/schule/informatik/lk/haskell/ratschlaege
Graham Hutton,
Cambridge University Press 2016
O'Sullivan, Goerzen, Stewart,
O'Reilly 2009
wurden in HTML unter Linux erstellt mit
alex@thinkpad ~ $ cowsay " Danke fuer euer Interesse! (:-) "
___________________________________
< Danke fuer euer Interesse! (:-) >
-----------------------------------
\ ^__^
\ (oo)\_______
(__)\ )\/\
||----w |
|| ||