Tutorium 3¶

Gruppen 5 und 7
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Übungsblätter¶

Blatt 1 Aufgaben 2 und 3 vollständig korrigiert und veröffentlicht
Next up: Blatt 1 Aufgabe 1 und Blatt 2
Digital in den nächsten Tagen, handschriftlich nächste Woche
Fragen? Probleme? (Praktomat?)

Wenn es sich irgend vermeiden lässt: Bitte keine handschriftlichen Code-Abgaben

Vorbemerkung 0¶

Haskell ist anders, aber lasst euch davon nicht verwirren!

Problem lesen
Algorithmus überlegen/nachschauen
Evtl. Pseudocode
Wie implementiere ich diesen Mechanismus in Haskell?

Mergesort, Horner-Schema: Nutzt die Algorithmen, die angegeben sind!

Vorbemerkung 1¶

f (x:xs) a
    | a = [x]
    | otherwise = x:xs

Wie kann man das schöner schreiben?

Zwei Optimierungsmöglichkeiten:

f (x:xs) True = [x]
f l False = l

...oder...

f l@(x:xs) a
    | a = [x]
    | otherwise = l

f l@(x:xs) a
    | a = [x]
    | otherwise = l
f [1,2,3] True
f [1,2,3] False

[1]

[1,2,3]

Vorbemerkung 2¶

Wie kann ich das folgende Codestück kürzer schreiben:

cmult p n = map (\x -> x*n) p

Currying!

cmult p n = map (*n) p

Vorbemerkung 3¶

Wie können wir folgende Ausdrücke eleganter schreiben:

take 10 (iterate (+1) 0)
take 10 (iterate (+2) 0)
takeWhile (<=10) (iterate (+2) 0)

[0,1,2,3,4,5,6,7,8,9]

[0,2,4,6,8,10,12,14,16,18]

[0,2,4,6,8,10]

take 10 [0..]
take 10 [0,2..]
[0,2..10]

[0,1,2,3,4,5,6,7,8,9]

[0,2,4,6,8,10,12,14,16,18]

[0,2,4,6,8,10]

Vorbemerkung 4: Endrekursion¶

Wiederholung: Wann ist etwas endrekursiv?
Wann Endrekursion nutzen?

Übungsblatt 2 - 1¶

Übungsblatt 2 - 2¶

a -> a

\x -> x

(a -> b) -> a -> b

\x -> x

(a -> b) -> (a -> b)

\x -> x

a -> b -> a

\x y -> x

Alle wohldefinierten, semantisch unterschiedlichen Funktionen des Typs
a -> a -> a

\x y -> x

\x y -> y

Leere Liste vom Typ [a]

[]

Einelementige Liste vom Typ [Int]

[42]

Leere Liste vom Typ [[a]]

[]

Liste vom Typ [[a]], die nur die leere Liste enthält.

[[]]

Warum gibt es keinen Wert, der für alle Typen a eine einelementige Liste von Typ [a] darstellt?

Enthaltener Wert? Es gibt kein null in Haskell

Gibt es einen Wert, der für alle Typen a eine einelementige Liste vom Type [[a]] darstellt?

Ja, nämlich:

[[]]

Geben Sie den Wert von [[[[[[[[[[[a]]]]]]]]]]] mit der kürzesten Schreibweise an

[]

Übungsblatt 2 - 3¶

type Polynom = [Double]

Polynom Multiplikation mit Konstante

cmult :: Polynom -> Double -> Polynom
cmult p c = map (*c) p

Polynom Auswertung mit dem Horner Schema
$$ a_0 + x * (a_1 + x * (a_2 + \dots (a_{n-1} + x * a_n) \dots) ) $$
```
eval :: Polynom -> Double -> Double
eval p x = foldr (\a v -> a + v*x) 0 p
```

Ableitung

deriv :: Polynom -> Polynom
deriv [] = []
deriv p  =zipWith (*) [1..] (tail p)

Typen¶

...schon wieder...

Jeder Ausdruck in Haskell hat einen Typ
Haskell ist damit statisch typisiert
Jeder Ausdruck wertet zu Werten des jeweiligen Typs aus
Typen werden automatisch inferiert

Polymorphe Typen¶

Beispiel: Listen-Typ

[t] ist der Typ von Listen mit Elementen vom Typ t
Typvariable t beliebig

Sichtweisen:

Typvariablen parametrisieren polymorphe Typen
Typkonstruktoren wie [ ] erzeugen neue Typen aus bestehenden

Vergleichbares in Java: Generics

LinkedList<T>

Funktionstypen¶

... sind polymorph, denn...

s -> t

... beschreibt den Typ aller Funktionen von s nach t (s,t beliebig)

Tupel¶

...sind polymorph, denn...

(,) :: s -> t -> (s,t)

...und umgekehrt...

fst :: (s,t) -> s
snd :: (s,t) -> t

Typsynonyme¶

Verbessert die Lesbarkeit:

type Polynom = [Double]

Explizite Typisierung¶

...kennen wir auch schon...

foldr :: (a -> b -> b) -> b -> [a] -> b

Übersichtlichkeit
Hilft beim Debugging

Übungsaufgaben zu Streams¶

Pseudozufallszahlen¶

$$ x_{i+1} = (a*x_i + b) mod m $$

Definiere rand :: [Integer] mit $$ m = 2^{16}, a = 25173, b = 13849, x_0 = 32 $$

-- Übungsaufgabe 3
a = 25173
b = 13849
rand = iterate (\x -> (a*x + b) `mod` (2^16)) 32
rand' = 32 : map (\x -> (a*x + b) `mod` (2^16)) rand'

take 10 rand
take 10 rand'

[32,32953,50566,6039,55612,20229,23746,18051,50584,401]

[32,32953,50566,6039,55612,20229,23746,18051,50584,401]

Fairer Münzwurf¶

Wir nutzen rand weiter Prozedur für fairen Münzwurf von Neumann:

Wir werfen unfaire Münze zwei Mal
Ergebnis gleich: Beginne von vorne
Ergebnis unterschiedlich: Nutze zweiten Wurf Unser Münzwurf: $x<2^{15}$ => 0, $x\geq2^{15}$ => 1

-- Übungsaufgabe 4
neumann :: [Bool]
unfairCoin = (map (\x -> x < 2^15) rand)
neumann = neumannHelper unfairCoin
    where neumannHelper (x:y:xs)
            | x==y = neumannHelper xs
            | otherwise = x : neumannHelper xs

take 10 neumann

[True,False,False,False,True,False,True,False,True,True]

Fairness Check¶

Wir zählen die Menge an Köpfen und Zahlen in den ersten $n$ Münzwürfen...

-- Übungsaufgabe 5
coinRatio :: Int -> Double
coinRatio n = count / ((fromIntegral n) - count)
    where count = fromIntegral (length (filter id (take n neumann)))

coinRatio 1000000

1.000040000800016

:t (/)
:t div

Lauflängen Kodierung¶

splitWhen p [] = ([],[])
splitWhen p l@(x:xs)
    | p x = ([],l)
    | otherwise = let (l1, l2) = splitWhen p xs in (x:l1, l2)

input = "aaaaaaabbbbbbccceeeedaaaaaabbbe"

splitWhen (/='a') input

runlength :: String -> [(Char, Int)]
runlength [] = []
runlength l@(x:xs) = (x, length a) : (runlength b)
    where 
        (a,b) = splitWhen (/=x) l
        asdf x
         |x = 1
         | otherwise = 2

runlength input

repeat' (c,0) = []
repeat' (c,n) = c : repeat' (c, (n-1))
repeat' ('a',4)

decode [] = ""
decode (x:xs) = (repeat' x) ++ (decode xs)

decode (runlength input)

("aaaaaaa","bbbbbbccceeeedaaaaaabbbe")

[('a',7),('b',6),('c',3),('e',4),('d',1),('a',6),('b',3),('e',1)]

"aaaa"

"aaaaaaabbbbbbccceeeedaaaaaabbbe"