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!

  1. Problem lesen
  2. Algorithmus überlegen/nachschauen
  3. Evtl. Pseudocode
  4. 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
In [1]:
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:

In [2]:
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]
In [3]:
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

Blatt2_1_Lsg.png

Ü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 $$

In [4]:
-- Ü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'
In [5]:
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
In [6]:
-- Ü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
Redundant bracket
Found:
(map (\ x -> x < 2 ^ 15) rand)
Why Not:
map (\ x -> x < 2 ^ 15) rand
In [7]:
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...

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

coinRatio 1000000
Redundant bracket
Found:
(fromIntegral n) - count
Why Not:
fromIntegral n - count
1.000040000800016
In [9]:
:t (/)
:t div
(/) :: forall a. Fractional a => a -> a -> a
div :: forall a. Integral a => a -> a -> a

Lauflängen Kodierung

In [10]:
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)
Redundant bracket
Found:
(x, length a) : (runlength b)
Why Not:
(x, length a) : runlength b
Redundant bracket
Found:
(c, (n - 1))
Why Not:
(c, n - 1)
Use foldr
Found:
decode [] = "" decode (x : xs) = (repeat' x) ++ (decode xs)
Why Not:
decode xs = foldr ((++) . repeat') "" xs
Redundant bracket
Found:
(repeat' x) ++ (decode xs)
Why Not:
repeat' x ++ (decode xs)
Redundant bracket
Found:
(repeat' x) ++ (decode xs)
Why Not:
(repeat' x) ++ decode xs
("aaaaaaa","bbbbbbccceeeedaaaaaabbbe")
[('a',7),('b',6),('c',3),('e',4),('d',1),('a',6),('b',3),('e',1)]
"aaaa"
"aaaaaaabbbbbbccceeeedaaaaaabbbe"