Wiederholung

Typen
 [1,2,3] :: [Int] -- usw ... 
curried functions
 add x y z :: Int -> Int -> Int -> Int 
polymorphe Typen
 length :: [a] -> Int  
:type
 :type init 
Programme sind Dateien mit Funktionsdefinitionen

syntactic sugar

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 
					

Basisklassen

Basisklassen

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
 (==) :: a -> a -> Bool 
 (/=) :: a -> a -> Bool 
Ord
 (<) :: a -> a -> Bool 
 (<=), (<), (>=), min, max 
Show
 show :: a -> String 
Read
 read :: String -> a
Klasse überladene Methoden
Num
 (+) :: a -> a -> a 
 (-), (*), negate, abs, signum
Integral
 div :: a -> a -> a 
 mod :: a -> a -> a 
Fractional
 (/) :: a -> a -> a 
 rezip :: a -> a -> a 

Probiert einfach mal die überladenen Methoden in ghci aus.

Funktionen definieren

Funktionen definieren

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 

Guarded Equations

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    

Pattern Matching

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 

Pattern Matching

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

Pattern Matching

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]

Der cons Operator

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

Lambda Expressions

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
					

... jetzt ihr ...

  1. Definiere eine Funktion 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])
    				
  2. Definiere eine Funktion third :: [a] -> a die das dritte Element einer Liste mit mindestens drei Elementen zurückliefert. Verwende dazu:
    1. head und tail
    2. List indexing (!!)
    3. pattern matching
  3. Definiere eine Funktion safetail :: [a] -> [a] die genau wie tail arbeitet, aber bei der leeren Liste keinen Fehler wirft. Verwende dabei die Funktionen tail und null.
    1. mit guarded Equations
    2. mit pattern matching

List Comprehensions

List Comprehensions

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]

					

eine Studie

Cäsar Verschlüsselung per Brute-Force knacken.

Holt euch nen Kaffee, lehnt euch zurück und schaut zu.

Rekursion

Rekursion

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.

Quicksort

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

... jetzt ihr ...

vollzieht die Beispiele selbst nach und probiert einfach mal aus.

Zum Selbermachen:
http://domay.de/schule/informatik/lk/haskell/ratschlaege

Quellen

  • Programming in Haskell

    Graham Hutton,
    Cambridge University Press 2016

  • Real World Haskell

    O'Sullivan, Goerzen, Stewart,
    O'Reilly 2009

  • https://www.haskell.org/

Die visuellen Hilfen

wurden in HTML unter Linux erstellt mit

einem einfachen Texteditor (vim)
Mozilla Firefox
dem augenfreundlichen Farbschema solarized dark von Ethan Schoonover (http://ethanschoonover.com/)
und reveal.js von Hakim El Hattab (http://hakim.se)


alex@thinkpad ~ $ cowsay " Danke fuer euer Interesse! (:-) "
 ___________________________________
<  Danke fuer euer Interesse! (:-)  >
 -----------------------------------
        \   ^__^
         \  (oo)\_______
            (__)\       )\/\
                ||----w |
                ||     ||