TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2009-04-02
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 = (43, [mnr!!0, mnr!!6], (head mnr, head name), (tail.tail) mnr)
-- t1 == (43,[0,6],(0,'M'),[2,3,4,5,6])
t2 = (\x -> \y -> (x.y.x))
-- t2 :: (a -> b) -> (b -> a) -> a -> b
t3 = t2 (sum) (\y -> [y,y]) (mnr)
-- t3 == 42
t4 = ([i | i <- mnr, i `mod` 2 == 0], [[i, 2*i] | i <- mnr])
-- t4 == ([0,2,4,6],[[0,0],[1,2],[2,4],[3,6],[4,8],[5,10],[6,12]])
t5 = [(i, [4,3..i]) | i <- (tail mnr)]
-- t5 == [(1,[4,3,2,1]),(2,[4,3,2]),(3,[4,3]),(4,[4]),(5,[]),(6,[])]
ml n l = reverse [l!!i | i<-[0..n-1], i < length l]
t6 = (ml 3 mnr, [(i,j) | i <- ml 3 mnr, j <- ml 3 mnr, i > j])
-- t6 == ([2,1,0],[(2,1),(2,0),(1,0)])
p [] = 5000
p [e] = e
p (a:b:l) | a <= b = p (b:l)
p (a:l) = p l + a + p l
t7 = (p [mnr!!6], p [mnr!!5, mnr!!6], p mnr)
-- t7 == (6,6,6)
Aufgabe 2[Bearbeiten | Quelltext bearbeiten]
5% Definieren Sie einen polymorphen algebraischen Datentypen ITree zur Darstellung von binären Bäumen. Knoten und Blätter sollen neben einem Integer ein polymorphes Element enthalten. Es gibt also keine leeren Blätter.
data ITree a = Node Integer a (ITree a) (ITree a) | Leaf Integer a
Aufgabe 3[Bearbeiten | Quelltext bearbeiten]
5% Geben Sie einen konkreten ITree-Baum mit genau zwei Knoten (und passend vielen Blättern) als Zeichnung und in Haskell Syntax an.
b1 = Node 1 'a' (Node 2 'b' (Leaf 3 'c') (Leaf 4 'd')) (Leaf 5 'e')
Aufgabe 4[Bearbeiten | Quelltext bearbeiten]
20% Definieren Sie "absteigend", das für einen konkreten Baum genau dann wahr (True) ist, wenn die folgenden 2 Bedingungen gelten: 1 - in allen Knoten ist der Integer Eintrag größer als die Integer Einträge der Unterbäume 2 - Alle Integer-Einträge (in Knoten und Blättern) des ersten Unterbaums sind größer als die des zweiten. absteigend::iTree a -> Bool
-->Unknown: Hier meine Lösung, bin mir aber nicht sicher, ob die stimmt!!!
groesserT:: ITree a -> ITree a -> Bool
groesserT (Leaf n _) (Leaf m _)
|n>m = True
|otherwise = False
groesserT (Leaf n _) (Node m _ t1 t2)
|n>m = True
|otherwise = False
groesserT (Node n _ t1 t2) (Leaf m _)
|n>m = True
|otherwise = False
groesserT (Node n _ t1 t2) (Node m _ t3 t4)
|n>m = True
|otherwise = False
absteigend:: ITree a ->Bool
absteigend (Leaf _ _) = True
absteigend t@(Node n _ t1 t2) =
groesserT t t1 &&
groesserT t t2 &&
groesserT t1 t2 &&
absteigend t1 &&
absteigend t2
-----------------------------------------------------------------------
meine Lösung
absteigend :: ITree a -> Bool
absteigend (Leaf _ _) = True
absteigend (Node i _ l r) = (i > getFirstInteger l) &&
(i > getFirstInteger r) &&
(minimum (iTreeToList l) > maximum (iTreeToList r)) &&
(absteigend l) &&
(absteigend r)
-- hilfs funktionen
getFirstInteger :: ITree a -> Integer
getFirstInteger (Leaf i _) = i
getFirstInteger (Node i _ _ _) = i
iTreeToList :: ITree a -> [Integer]
iTreeToList (Leaf i _) = [i]
iTreeToList (Node i _ l r) = [i] ++ (iTreeToList l) ++ (iTreeToList r)
-----------------------------------------------------------------------
eine kürzere (aber ineffizientere) Lösung
absteigend :: ITree a -> Bool
absteigend (Leaf _ _) = True
absteigend (Node i _ l r) = (i > maximum (iTreeToList l)) &&
(i > maximum (iTreeToList r)) &&
(minimum (iTreeToList l) > maximum (iTreeToList r)) &&
(absteigend l) &&
(absteigend r)
-- hilfs funktionen
iTreeToList :: ITree a -> [Integer]
iTreeToList (Leaf i _) = [i]
iTreeToList (Node i _ l r) = [i] ++ (iTreeToList l) ++ (iTreeToList r)
-----------------------------------------------------------------------
eine Lösung ohne Hilfsfunktion, nur mit Pattern-Matching.
isg :: ITree a -> Bool
isg (Leaf _ _) = True
isg (Node i _ (Node left_i c1 l1 r1) (Node right_i c2 l2 r2))
| i < left_i || i < right_i || left_i < right_i = False
| otherwise = and [isg (Node left_i c1 l1 r1), isg (Node right_i c2 l2 r2)]
isg (Node i _ (Node left_i c1 l1 r1) (Leaf right_i _))
| i < left_i || i < right_i || left_i < right_i = False
| otherwise = and [isg (Node left_i c1 l1 r1)]
isg (Node i _ (Leaf left_i _) (Node right_i c2 l2 r2))
| i < left_i || i < right_i || left_i < right_i = False
| otherwise = and [isg (Node left_i c2 l2 r2)]
isg (Node i _ (Leaf left_i _) (Leaf right_i _))
| i < left_i || i < right_i || left_i < right_i = False
| otherwise = True
-----------------------------------------------------------------------
Testcases:
itree2 = Node 100 'a' (Node 10 'b' (Leaf 9 'l') (Leaf 6 'l')) (Leaf 2 'l')
-- N:100,a
-- / \
-- N:10,b L:2,l
-- / \
-- L:9,l L:6,l
itree3a = Node 100 'a' (Node 7 'b' (Leaf 5 'l') (Leaf 4 'l')) (Leaf 14 'l')
-- N:100,a
-- / \
-- N:7,b L:14,l
-- / \
-- L:5,l L:4,l
itree3b = Node 100 'a' (Node 17 'b' (Leaf 5 'l') (Leaf 8 'l')) (Leaf 14 'l')
-- N:100,a
-- / \
-- N:17,b L:14,l
-- / \
-- L:5,l L:8:,l
itree4 = Node 100 'a' (Node 7 'b' (Leaf 5 'l') (Leaf 4 'l')) (Node 14 'b' (Leaf 5 'l') (Leaf 4 'l'))
-- False weil 14 > 7
-- N:100,a
-- / \
-- N:7,b N:14,b
-- / \ / \
-- L:5,l L:4,l L:5,l L:4,l
itree5 = Node 100 'a' (Node 17 'b' (Leaf 5 'l') (Leaf 4 'l')) (Node 14 'b' (Leaf 5 'l') (Leaf 4 'l'))
-- True
-- N:100,a
-- / \
-- N:17,b N:14,b
-- / \ / \
-- L:5,l L:4,l L:5,l L:4,l
itree6 = Node 100 'a' (Leaf 17 'l') (Leaf 14 'l')
-- True
-- N:100,a
-- / \
-- L:17,b L:14,b
itree7a = Node 100 'a' (Leaf 7 'l') (Leaf 14 'l')
-- True
-- N:100,a
-- / \
-- L:7,b L:14,b
itree7b = Node 100 'a' (Leaf 17 'l') (Leaf 14 'l')
-- True
-- N:100,a
-- / \
-- L:17,b L:14,b
--------------------------------------
Lösung von r0f1:
absteigend :: ITree a -> Bool
absteigend (Leaf a _) = True
absteigend (Node a _ l r)
| val l >= a || val r >= a = False -- 1
| val l <= val r = False -- 2
| otherwise = absteigend l && absteigend r
where
val (Node x _ _ _) = x
val (Leaf x _) = x
--------------------------------------
Aufgabe 5[Bearbeiten | Quelltext bearbeiten]
20%Definieren Sie alle_ab, das bein Durchwandern eines Baums alle ab einem konkreten Integer Eintrag vorkommenden (polymorphen) Elemente als Paare liefert. Ein Knoten wird in der Reihenfolge Knotenelement, dann linker und dann rechter Unterbaum durchwandert. Ist kein passender Eintrag vorhanden, ergebe die Funtkion die leere Liste. Gibt es den passenden Integer Eintrag, so enthält das Ergebnis jedenfalls ein Element alle_ab :: iTree a -> Integer -> [(Integer,a)]
alle_ab :: ITree a -> Integer -> [(Integer,a)]
alle_ab (Leaf n a) m |n>m = [(n,a)]
|otherwise = []
alle_ab (Node n a t1 t2) m | n>m = [(n,a)] ++ alle_ab t1 m ++ alle_ab t2 m
|otherwise = alle_ab t1 m ++ alle_ab t2 m
andere lösung by bonomat, 28.02.10
ich hab das anders verstanden, alle_ab solle alles ausgeben sobald er den gewünschten integer wert im baum findet: z.b.
alle_ab (Node 1 'a' (Leaf 2 'b') (Leaf 3 'c')) 2 == [(2,'b'),(3,'c')]
alle_ab (Node 1 'a' (Leaf 2 'b') (Leaf 1 'c')) 1 == [(1,'a'),(2,'b'),(1,'c')]
hier meine lösung dazu:
alle_ab :: ITree a -> Integer -> [(Integer,a)]
alle_ab a@(Node x b _ _) i = alle_ab2 (ttreetolist a) i
alle_ab2 :: [(Integer, a)] -> Integer -> [(Integer, a)]
alle_ab2 [] a = []
alle_ab2 (x:xs) a
| fst(x) == a = (x:xs)
| otherwise = alle_ab2 (xs) a
ttreetolist :: ITree a -> [(Integer, a)]
ttreetolist (Leaf n b) = [(n,b)]
ttreetolist (Node n b t1 t2) = [(n,b)] ++ ttreetolist t1 ++ ttreetolist t2
sehe ich wie bonomat. meine lösung:
ttl :: ITree a -> [(Integer, a)]
ttl (Leaf x a) = [(x,a)]
ttl (Node x a t1 t2) = (x,a) : (ttl t1) ++ (ttl t2)
alle_ab :: ITree a -> Integer -> [(Integer,a)]
alle_ab t y = dropWhile (\x -> (fst x) /= y) (ttl t)