TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2012-03-02
Aufgabe 1[Bearbeiten | Quelltext bearbeiten]
(50%) Werten Sie die Ausdrücke aus oder bestimmen Sie deren allgemeinsten Typ.
mnr = [0,8,2,4,7,5,1] :: [Int]
name = "Max Mustermann" :: String
kzn = "987654" :: String
t1 = ("p1", unlines ((:) ((head.words) name) ["!"]))
{- t1 == ("p1", "Max\n!\n") -}
t2 = (\x y z a -> ((x.y) z, (y.x) z))
{- t2 :: (a -> a) -> (a -> a) -> a -> b -> (a,a) -}
-- ???
tx = take 4 [[i | j <- [i..5]] | i <- mnr]
{- tx == [[0,0,0,0,0,0],[],[2,2,2,2],[4,4]] -}
p o (a:l) (b:m) n = o a b : p o l m n
p _ _ _ n = n
{- p :: (a -> b -> c) -> [a] -> [b] -> [c] -> [c] -}
t7 = p (+) (reverse mnr) mnr [11]
{- t7 == ([1,13,9,8,9,13,1,11]) -}
Aufgabe 2[Bearbeiten | Quelltext bearbeiten]
(5%) Definieren Sie einen polymorphen Datentyp TTree, der einen ternären Baum darstellt. Dabei haben innere Knoten genau drei Unterbäume. Blätter haben entweder ein polymorphes Element oder sind leer.
data TTree a = Nil
| Leaf a
| Node (TTree a) (TTree a) (TTree a)
Aufgabe 3[Bearbeiten | Quelltext bearbeiten]
(5%) Definieren und zeichnen Sie einen Baum des Typs (TTree (TTree Integer)) der genau die beiden Datenelemente 1 und 2 enthält.
tree = Leaf (Node (Leaf 1) (Leaf 2) Nil)
Aufgabe 4[Bearbeiten | Quelltext bearbeiten]
(15% + 5%) Definieren Sie das Prädikat geordnet, das genau dann True zurückliefert wenn für jeden Knoten gilt:
- alle polymorphen Elemente des ersten Unterbaums sind kleiner als alle polymorphen Elemente des zweiten Unterbaums
- alle polymorphen Elemente des zweiten Unterbaums sind kleiner als alle polymorphen Elemente des dritten Unterbaums
Definieren Sie außerdem eine Typklasse für geordnet.
geordnet :: Ord a => TTree a -> Bool
geordnet Nil = True
geordnet (Leaf a) = True
geordnet (Node x y z) = and [help y x, help z y, geordnet x, geordnet y, geordnet z]
help :: Ord a => TTree a -> TTree a -> Bool
help _ Nil = True
help Nil _ = True
help a b
| flatten a == [] || flatten b == [] = True
| otherwise = minimum (flatten a) > maximum (flatten b)
flatten :: TTree a -> [a]
flatten Nil = []
flatten (Leaf a) = [a]
flatten (Node x y z) = flatten x ++ flatten y ++ flatten z
test = and [geordnet tree1 == True, geordnet tree2 == False, geordnet tree3 == False, geordnet tree4 == True]
tree1 = (Node (Leaf 1) (Leaf 2) (Leaf 3))
tree2 = (Node (Node (Leaf 1) (Leaf 2) (Leaf 3)) (Leaf 2) Nil)
tree3 = (Node (Node (Leaf 1) (Leaf 2) (Node (Leaf 5) (Leaf 4) Nil)) (Leaf 10) Nil)
tree4 = (Node (Node (Leaf 1) (Leaf 2) (Node (Leaf 4) (Leaf 9) Nil)) (Leaf 10) Nil)
Alternativ:
class Ordnung a where
geordnet :: a -> Bool
instance Ord a => Ordnung (TTree a) where
geordnet tree
| f == [] = True
| otherwise = and $ zipWith (<) f (tail f)
where f = flatten tree
Lösungsvorschlag von Stampi:
geordnet :: Ord a => TTree a -> Bool
geordnet Nil = True
geordnet (Leaf a) = True
geordnet (Node Nil middle right) = test middle right
geordnet (Node left middle Nil) = test left middle
geordnet (Node left Nil right) = test left right
geordnet (Node left middle right)
= test left middle && test middle right
test :: Ord a => TTree a -> TTree a -> Bool
test f s =
((maximum (asList f)) < (minimum (asList s)))
asList :: TTree a -> [a]
asList Nil = []
asList (Leaf a) = [a]
asList (Node left middle right) = (asList left) ++ (asList middle) ++ (asList right)
class Ordnung a where
isGeordnet :: a -> Bool
instance Ord a => Ordnung (TTree a) where
isGeordnet = geordnet
-- bei dieser Lösung werden nicht alle Knoten überprüft, sondern nur die Wurzel. Es fehlen die rekursiven Aufrufe bei geordnet.
Aufgabe 5[Bearbeiten | Quelltext bearbeiten]
(15% + 5%) Definieren Sie eine Funktion zipT, die zwei ternäre Bäume zu einem zusammenfügt. Wenn bei den zwei Bäumen an derselben Stelle ein innerer Knoten liegt, soll bei dem returnierten Baum an dieser Stelle auch ein innerer Knoten liegen. Wenn sich an derselben Stelle ein Blatt befindet, hat der returnierte Baum dort auch ein Blatt, das ein Paar der polymorphen Elemente als Eintrag hat. An allen anderen Stellen soll ein leeres Blatt liegen. Definieren Sie die Funktion so allgemein wie möglich.
zipT :: TTree a -> TTree b -> TTree (a,b)
zipT (Node t11 t12 t13) (Node t21 t22 t23) = Node (zipT t11 t21) (zipT t12 t22) (zipT t13 t23)
zipT (Leaf v1) (Leaf v2) = Leaf (v1,v2)
zipT _ _ = Nil