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

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)

Diskussion dazu im Forum

Aufgabe 2

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

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

20% Definieren sie aufsteigend, das fuer einen konkreten Baum genau dann wahr (True) ist wenn die folgenden drei Bedingungen gelten:

1. In allen Knoten ist der Integer-Eintrag kleiner als die Integer-Eintraege der Unterbaeume.
2. Alle Integer-Eintraege des ersten Unterbaumes sind kleiner als die des zweiten.
3. 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

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

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

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)