TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2009-03-05
mnr = [_,_,_,_,_,_,_] :: [Integer]
name = "_______________" :: String
knz = "_____________" :: String
(Die personenbezogenen Daten wurden bei der Errechnung der Werte in Aufgabe 1 verwendet)
Aufgabe 1[Bearbeiten | Quelltext bearbeiten]
50% Geben sie den Wert bzw. allgemeinsten Typ fuer t1 bis t7 an! (Die Werte sind mit mnr=[0,1,2,3,4,5,6] und name = "Mustermann, Max" zustande gekommen)
t1 = (23, (mnr!!0, mnr!!6), (head mnr, head name), tail tail mnr);
-- t1 == (23,(0,6),(0,'M'),[2,3,4,5,6])
t2 = (\x -> \y -> (x (y x), x, y))
-- t2 :: (a -> b) -> ((a -> b) -> a) -> (b,a -> b,(a -> b) -> a)
t3 = (\(x,_,_)->x) (t2(\x->x+1)(\x->mnr!!6))
-- t3 == 7
t4 = ([i|i<-mnr, i>4], [(i, i+1)| i<-mnr])
-- t4 == ([5,6],[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7)])
ml n l = reverse [l!!x | x <- [n-1, n-2 .. 0], x < (length l)]
t5 = (ml 3 mnr, [(a,b) | a <- ml 3 mnr, b <- ml 3 mnr, a < b])
-- ([0,1,2],[(0,1),(0,2),(1,2)])
p [] = 3000
p [e] = e
p (a:b:l) = p l + a+b + p l
t6 = (p [mnr!!6], p [mnr !! 5, mnr !! 6], p mnr)
-- (6,6011,95)
Aufgabe 2[Bearbeiten | Quelltext bearbeiten]
5% Definieren sie einen polymorphen algebraischen Datentyp NumTree zur Darstellung von ternaeren Baeumen. Die Knoten sollen neben einem Element Integer und einem polymorphen Element drei NumTree-Unterbaeume enthalten. Es gibt also keine eigenen Blaetter sondern nur Knoten mit leeren Unterbaeumen als Blaetter.
data NumTree a = NT Integer a (NumTree a) (NumTree a) (NumTree a) | Nil
Aufgabe 3[Bearbeiten | Quelltext bearbeiten]
5% Geben sie einen konkreten NumTree-Baum mit zwei Knoten als Zeichnung und in Haskell-Syntax an.
b3 = NT 1 'a' (NT 2 'b' Nil Nil Nil) Nil Nil
Aufgabe 4[Bearbeiten | Quelltext bearbeiten]
20% Definieren sie aufsteigend, das fuer einen konkreten Baum genau dann wahr (True) ist wenn die folgenden drei Bedingungen gelten:
- In allen Knoten ist der Integer-Eintrag kleiner als die Integer-Eintraege der Unterbaeume.
- Alle Integer-Eintraege des ersten Unterbaumes sind kleiner als die des zweiten.
- Alle Integer-Eintraege des zweiten Unterbaumes sind kleiner als die des dritten.
aufsteigend :: NumTree a -> Bool
aufsteigend Nil = True
aufsteigend t@(NT x _ Nil v w) =
treesmaller t v && treesmaller t w &&
treesmaller v w &&
aufsteigend v && aufsteigend w
aufsteigend t@(NT x _ u v w) =
treesmaller t u && treesmaller t v && treesmaller t w &&
treesmaller u v && treesmaller v w &&
aufsteigend u && aufsteigend v && aufsteigend w
treevals :: NumTree a -> [Integer]
treevals Nil = []
treevals (NT x _ u v w) = x : (us ++ vs ++ ws)
where us = treevals u; vs = treevals v; ws = treevals w
treesmaller :: NumTree a -> NumTree a -> Bool
treesmaller Nil _ = True
treesmaller _ Nil = True
treesmaller u v = (maximum (treevals u)) < (minimum (treevals v))
Fehler:
mit maximum & minimum liefert immer False zurück.
Richtig wäre:
treesmaller u v = (head (treevals u)) < (head(treevals v))
andere Version:
aufsteigend :: NumTree a -> Bool
aufsteigend Nil = True
aufsteigend t@(NT x _ u v w) =
treesmaller t u &&
treesmaller t v &&
treesmaller t w &&
treesmaller u v &&
treesmaller v w &&
aufsteigend u &&
aufsteigend v &&
aufsteigend w
treesmaller :: NumTree a -> NumTree a -> Bool
treesmaller Nil _ = True
treesmaller _ Nil = True
treesmaller (NT x _ u v w) (NT y _ u1 v1 w1)
| x < y = True
| otherwise = False
Anscheinend sind beide Lösungen fehlerhaft! Siehe folgendes Beispiel:
NodeNT 1 'a' (NT 2 'b' Nil Nil Nil) (NT 3 'c' Nil (NT 10 'x' Nil Nil Nil) Nil) (NT 4 'd' Nil Nil Nil)
Ergibt bei beiden 'True', obwohl der Knoten 10 'x' größer ist als 4 'd'.
Hier noch meine Lösung:
aufsteigend :: NumTree a -> Bool
aufsteigend (Nil) = True
aufsteigend (NT x _ t1 t2 t3) =
checkRule1 t1 x &&
checkRule1 t2 x &&
checkRule1 t3 x &&
checkRule2And3 t1 t2 &&
checkRule2And3 t2 t3 &&
aufsteigend t1 &&
aufsteigend t2 &&
aufsteigend t3
treeToList :: NumTree a -> [Integer]
treeToList (Nil) = []
treeToList (NT x _ t1 t2 t3) = [x] ++ treeToList t1 ++ treeToList t2 ++ treeToList t3
checkRule1 :: NumTree a -> Integer -> Bool
checkRule1 Nil x = True
checkRule1 (NT n _ t1 t2 t3) x
| x < n = True
| otherwise = False
checkRule2And3 :: NumTree a -> NumTree a -> Bool
checkRule2And3 Nil _ = True
checkRule2And3 _ Nil = True
checkRule2And3 t1 t2 = maximum(treeToList t1) < minimum(treeToList t2)
Hier eine Lösung, die IMHO korrekt und kurz ist:
aufsteigend :: NumTree a -> Bool
aufsteigend t =
snd (foldl (\(x,y) z -> (z,y && (x < z))) (p,True) ps)
where
(p:ps) = flatten t
flatten :: NumTree a -> [Integer]
flatten Nil = []
flatten (Node i a t1 t2 t3) = [i] ++ flatten t1 ++ flatten t2 ++ flatten t3
noch eleganter:
aufsteigend' :: NumTree a -> Bool
aufsteigend' t = l == sort l
where
l = (flatten t)
Alternative Lösung zu Aufgabe 4[Bearbeiten | Quelltext bearbeiten]
-- Aufruf: aufsteigend b3
data NumTree a = Node Integer a (NumTree a) (NumTree a) (NumTree a)
| Nil
b3 = Node 15 'a' (Node 16 'b' Nil (Node 17 'c' Nil Nil Nil) Nil) Nil Nil
aufsteigend :: NumTree a -> Bool
aufsteigend Nil = True
aufsteigend (Node x _ t1 t2 t3) =
let
b1 = getBiggest t1 0
b2 = getBiggest t2 0
b3 = getBiggest t3 0
in
(allBigger x t1) &&
(allBigger x t2) &&
(allBigger x t3) &&
( if (isNil t2) then True else b1 < b2 ) &&
( if (isNil t3) then True else b2 < b3 ) &&
aufsteigend t1 &&
aufsteigend t2 &&
aufsteigend t3
isNil :: NumTree a -> Bool
isNil Nil = True
isNil _ = False
allBigger :: Integer -> NumTree a -> Bool
allBigger _ Nil = True
allBigger m (Node x _ t1 t2 t3)
| m < x = (allBigger x t1) && (allBigger x t2) && (allBigger x t3)
| otherwise = False
getBiggest :: (NumTree a) -> Integer -> Integer
getBiggest Nil m = m
getBiggest (Node x _ t1 t2 t3) m =
let
big = if m > x then m else x
in
maximum [(getBiggest t1 big),(getBiggest t2 big),(getBiggest t3 big)]
Alternative Lösung zu Aufgabe 4[Bearbeiten | Quelltext bearbeiten]
Ebenfalls kurz, weniger elegant, aber einfach zu verstehen.
validateTree::(NumTree a)->Bool
validateTree Nil = True
validateTree (Node a _ l m r) = (compareV a l) && (compareT l m) && (compareT m r) && validateTree l && validateTree m && validateTree r
compareT::NumTree a->NumTree a->Bool
compareT Nil _ = True
compareT _ Nil = True
compareT (Node a _ _ _ _) (Node b _ _ _ _) = (a<b)
compareV::Integer->NumTree a->Bool
compareV _ Nil = True
compareV a (Node b _ _ _ _) = a<b
Aufgabe 5[Bearbeiten | Quelltext bearbeiten]
20% Definieren sie allegroesser, das in beliebiger Reihenfolge alle Elemente jener Knoten zurueckliefert, deren Integer-Eintrag groesser als der uebergebene Wert ist.
allegroesser :: NumTree a -> Integer -> [a]
allegroesser Nil _ = []
allegroesser (NT x y u v w) n =
if x > n then y : rest
else rest
where rest = (allegroesser u n) ++ (allegroesser v n) ++ (allegroesser w n)