Tutorium 3

Gruppen 2 und 4
Samuel Teuber
propa@teuber.dev
https://teuber.dev/propa

Übungsblätter

• Fragen? Probleme? (Praktomat?)

UMFRAGE

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: 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

f x
  | even x = x `div` 2
  | odd x = (x-1) `div` 2
  
f' x = x `div` 2

f 5
f' 5

2

2

Aufgabe 1: Polynome

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)
  

Aufgabe 2: Collatz

• Unendliche Liste der Folgenmitglieder für Startwert a0

  collatz :: Int -> [Int]
  collatz m = iterate next m
    where
            next :: Int -> Int
            next an
                | an `mod` 2 == 0 = an `div` 2
                | otherwise = 3 * an + 1
  

• Zählen bis zur ersten 1

  num m = length (takeWhile (/= 1) (collatz m)))
  

• Suche nach maximalem num in Interval

  maxNum a b = foldl maxPair (0,0) (map (\m -> (m, num m)) [a..b])
    where maxPair (m,n) (m',n') = if n > n' then (m,n) else (m',n')
  

Aufgabe 3: Prime Powers

Klausuraufgabe

• Merge auf unendlichen Listen

  merge [] b = b
  merge a [] = a
  merge l1@(x:xs) l2@(y:ys)
    | (x<y) = x:merge xs l2
    | otherwise = y:merge l1 ys
  

• Erste $n$ Potenzen aller Primzahlen

  primepowers n = foldr merge [] [map (^i) primes | i <- [1..n]]
  

B-Seite: Termsprachen

Umfrage

Noch ein Wort zur Frage von letzter Woche...

Typ [I]: (a -> a) -> (a -> a)
Typ [II]: a -> a

Wenn eine Funktion Typ [II] hat, "dann hat sie eigentlich auch Typ [I]"

Wenn eine Funktion Typ [II] hat, dann kann man sie verwenden als hätte sie Typ [I]

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

...schon wieder...

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

Wollen wir statt Klassen einfach Tupel benutzen?

type Name = (String, String)
type MNumber = Integer -- Für die Addition von Matrikelnummern...
type Address = (String, Integer, String) -- Straße, PLZ und Ort
type Grades = [(String, Double)] -- Fach Name und Note
type Student = (Name,MNumber, Address, Grades)

Ist das eine gute Idee?

NEIN

• Tupel könnte für beliebige Werte benutzt werden
• Kaum/Keine explizite Bedeutung

Algebraische Datentypen

Definition neuer Typen durch Auflistung aller Konstruktoren:

data Address = Address String Integer String
data UniversityPerson = Student String Integer Address
                        | Professor String Address

Ergibt die folgenden Konstruktoren:

Address :: String -> Integer -> String -> Address
Student :: String -> Integer -> Adress -> UniversityPerson
Professor :: String -> Adress -> UniversityPerson

Jede*r Student und jede*r Professor ist eine UniversityPerson

Pattern-Matching

data UniversityPerson = Student String Integer
                        | Professor String
getName :: UniversityPerson -> String
getName (Student name _) = name
getName (Professor name)  = name

getName (Student "Samuel" 424242)
getName (Professor "Prof. Dr. Snelting")

"Samuel"

"Prof. Dr. Snelting"

Polymorphe Algebraische Datentypen

z.B. Realisierung von optionalen Werten:

data Maybe t = Nothing | Just t
Just True :: Maybe Bool

Polymorphe Algebraische Datentypen (2)

data Either t s = Option1 t | Option2 s

-- Übungsaufgabe 1 (2min)
process :: (t -> a) -> (s -> a) -> Either t s -> a
process f _ (Option1 a) = f a
process _ g (Option2 b) = g b

printBool :: Bool -> String
printBool False = "Aww, it's false"
printBool True = "Yay, it's true"

printInt :: Int -> String
printInt x
    | x<=0 = "Nope, not gonna spread this negativity"
    | (x>0) && (x<100) = "This number is pretty small"
    | otherwise = "Woah that's a big number"
  
print' = process printBool printInt

:t print'
print' (Option1 False)
print' (Option2 (-101))

print' :: Either Bool Int -> String

"Aww, it's false"

"Nope, not gonna spread this negativity"

Polymorphe Rekursive Algebraische Datentypen

data Tree t = Leaf t | Node (Tree t) t (Tree t)

-- Übungsaufgabe 2:
-- Definiere einen polymorphen Datentyp für einfach verkettete Listen
-- Definiere eine Operation zur Berechnung der Listenlänge
data List a = End | Part a (List a)

listLength :: List a -> Int
listLength End = 0
listLength (Part a l) = 1 + (listLength l)

listLength (Part 2 End)

Redundant bracket

Found:

1 + (listLength l)

Why Not:

1 + listLength l

1

Typklassen

...endlich...

• Zusammenfassen von Typen anhand von definierter Operationen
• Java: ~Interfaces Beispiel Eq:

  class Eq t where
    (==) :: t -> t -> Bool
    (/=) :: t -> t -> Bool
  

  Default Implementierungen:

  x /= y = not (x == y)
    x == y = not (x /= y)
  

Typklassen implementieren

instance Eq Bool where
    True == True = True
    False == False = True
    x == y = False

Auch für Polymorphe Typen:

data Maybe t = Nothing | Just t

class Defaultable t where
    getDefault :: t a -> a -> a
    
instance Defaultable Maybe where
    getDefault (Just x) c = x
    getDefault Nothing c = c

getDefault Nothing 1
getDefault (Just 10) 1

1

10

Typklassen Vererbung

:t foldr

foldr :: forall (t :: * -> *) a b. Foldable t => (a -> b -> b) -> b -> t a -> b

Automatische Instanziierung

...für algebraische Datenstrukturen
Basierend auf innenliegenden Typen:

data Shape = Circle Double | Rectancle Double Double deriving Eq

Übungsaufgabe

Befindet sich ein Element in einem Baum?

-- Übungsaufgabe 3
data Tree t = Leaf t | Node (Tree t) t (Tree t)

treeFind :: (Eq a) => Tree a -> a -> Bool
treeFind (Leaf x) y = x == y
treeFind (Node x y z) a = treeFind x a || y==a || treeFind z a

myTree = Node (Node (Leaf "test") "foo" (Leaf "tset")) "abc" (Node (Leaf "42") "bar" (Leaf "24") )
treeFind myTree "test"
treeFind myTree "thisisnotinmytree"

True

False

Übungsaufabe

map aber für Bäume

-- Übungsaufgabe 4
data Tree t = Leaf t | Node (Tree t) t (Tree t) deriving Show

treeMap :: (a->b) -> Tree a -> Tree b
treeMap f (Leaf x) = Leaf (f x)
treeMap f (Node l x r) = Node (treeMap f l) (f x) (treeMap f r)

myTree = Node (Node (Leaf "test") "foo" (Leaf "tset")) "abc" (Node (Leaf "42") "bar" (Leaf "24") )
treeMap tail myTree

Node (Node (Leaf "est") "oo" (Leaf "set")) "bc" (Node (Leaf "2") "ar" (Leaf "4"))

Übungsaufgabe

Typklasse für Datenstrukturen die Mappable sind.

Wir wollen:

• Typklasse die uns die Funktion dMap auf algebraischen Datentypen mit einem Parameter erlaubt

  class Mappable -- ...
  

• Eine Implementierung dieser Typklasse für Tree

  instance Mappable Tree -- ...
  

-- Übungsaufgabe 5
class Mappable t where
    dMap :: (a->b) -> t a -> t b

instance Mappable Tree where
    dMap f t = treeMap f t

Eta reduce

Found:

dMap f t = treeMap f t

Why Not:

dMap = treeMap

Quickcheck

Feedback