TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2012-03-02

Aufgabe 1

(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

(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

(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

(15% + 5%) Definieren Sie das Prädikat geordnet, das genau dann True zurückliefert wenn für jeden Knoten gilt:

1. alle polymorphen Elemente des ersten Unterbaums sind kleiner als alle polymorphen Elemente des zweiten Unterbaums
2. 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

(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