TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2011-06-09

Die Aufgaben waren wieder sehr ähnlich den letzten Prüfungen mit ein paar kleinen Gemeinheiten.

Aufgabe 1

z.B: mnr = [0,1,2,3,4,5,6]

t2 = (\x y z -> y.z.z);
-- t2 :: a -> (b -> c) -> (b -> b) -> b -> c

t3 = t2 sum reverse reverse mnr
-- t3 == [6,5,4,3,2,1,0]

p (e:t) = 2 * (p t) + e - p t
p _ = 100;
t7 = (p [mnr!!5, mnr!!6], p mnr)
-- t7 = (111,121)

Aufgabe 2

Polymorphen Datentyp TTree definieren: darzustellen ist ein Ternärer Baum mit einem polymorphen Datentyp und Null.

data TTree a = Nil | Node a (TTree a) (TTree a) (TTree a)

Aufgabe 3

Zeichnen sie einen Baum mit genau zwei Knoten die die String Werte "a" und "bc" enthalten und geben sie den Haskell-Syntax an.

baum = Node "a" Nil Nil (Node "bc" Nil Nil Nil)

Aufgabe 4

Durchmustern des ganzen Baumes, und True, falls immer alle Subknoten in allen Subbäumen größer sind, als der Wert eines Knotens

alleGroesser :: Ord a => (TTree a) -> Bool
alleGroesser Nil = True
alleGroesser (Node a one two three) = 
	if	alleGroesserAls one min
		&& alleGroesserAls two min
		&& alleGroesserAls three min then	True
	else						False
	where
		min = a


alleGroesserAls :: Ord a => (TTree a) -> a -> Bool
alleGroesserAls Nil _ = True
alleGroesserAls (Node a one two three) min =
	if	a > min
		&& (alleGroesserAls one newMin)
		&& (alleGroesserAls two newMin)
		&& (alleGroesserAls three newMin) then	True
	else						False
	where
		newMin = a

Elegantere Lösung:

flatten :: TTree a -> [a]
flatten Nil = []
flatten (Node a l m r) = [a] ++ flatten l ++ flatten m ++ flatten r

alleGroesser :: Ord a => TTree a -> Bool
alleGroesser Nil = True
alleGroesser (Node a l m r)
| filter (<a) (flatten l ++ flatten m ++ flatten r) == [] = True && alleGroesser l && alleGroesser m && alleGroesser r
|otherwise = False

Aufgabe 5

Alle Werte in irgendeiner Reihenfolge ausgeben, die größer sind, als der übergebene Wert.

groesserAls :: Ord a => (TTree a) -> a -> [a]
groesserAls Nil _ = []
groesserAls (Node a one two three) min =
	if a > min then
		[a]
		++ (groesserAls one min)
		++ (groesserAls two min)
		++ (groesserAls three min)
	else
		(groesserAls one min)
		++ (groesserAls two min)
		++ (groesserAls three min)

Elegantere Lösung (flatten-Funktion von Aufgabe 4 benötigt!):

alleGroesserAls :: Ord a => TTree a -> a -> [a]
alleGroesserAls Nil _ = []
alleGroesserAls tree a = filter (>a) (flatten tree)