TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2013-01-17

Forum

Diskussion im Forum dazu: https://web.archive.org/web/*/www.informatik-forum.at/showthread.php?99370-alte-pr%FCfung-17-1-2013

Aufgabe 1

(50%) Geben Sie Wert bzw. allgemeinsten Typ für t1 bis t7 an!

mnr = [0,1,2,3,4,5,6]  :: [Int]
name = "Max Mustermann" :: String
kzn = "e53X" :: String

t1 = ("p1",(take 2.tail)mnr, (take 3.words.(let no n= name;in no))"No");
{- t1 == ("p1",[1,2],["Max","Mustermann"]) -}

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

t3 = t2 (take 4) (\x->x++x) reverse mnr;
{- t3 == [0,1,2,3,0,1,2,3] -}

t4 = [[i+2]|i<-mnr,i+2<5] ++ [[i|i<-mnr,3<i,i>4]]];
{- t4 == [[2],[3],[4],[5,6]] -}

t5 = [[2..i]|i<-[i|i<-mnr,i>2],i<9];
{- t5 == [[2,3],[2,3,4],[2,3,4,5],[2,3,4,5,6]] -}

ml n l = drop 5 l ++ take n l
t6 = ( ml 2 mnr, take 5[(i,j)|i<- ml 2 mnr, j<- ml 2 mnr, j>=i ]);
{- t6 == ([5,6,0,1],[(5,5),(5,6),(6,6),(0,5),(0,6)]) -}

p (a:b:l) xs ys = p l (a:b:xs) (b:ys);
p _ xs ys = (sum xs, product ys);
t7 = ( p (drop 4 mnr) [1] [], p mnr [1] []);
{- t7 == ((10,5),(16,15)) -}

Aufgabe 2

(5%) Definieren Sie einen polymorphen algebraischen Datentyp BTplus zur Darstellung von binären Bäumen. Knoten enthalten neben einem polymorphen Element zwei Unterbäume. Weiters gibt es auch leere Bäume und leere Unterbäume.

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

Aufgabe 3

(5%) Geben Sie einen konkreten Wert des Typs (BTplus String, BTplus (BTplus Integer)), der die Werte 1, 2 und "ab" enthält, in Haskell-Syntax und als Zeichnung an.

((Node "ab" Nil Nil), (Node (Node 1 Nil Nil) (Node (Node 2 Nil Nil) Nil Nil) Nil))

Aufgabe 4

(5+15%) Definieren Sie sym, das für zwei Bäume des Typs BTplus genau dann True ist, wenn sie die gleiche Knotenstruktur besitzen und die Elemente des ersten Baums alle verschieden sind. Geben Sie für sym die entsprechende Typdeklaration an (Typklasse!)

flatten :: BTplus a -> [a]
flatten Nil = []
flatten (Node a a1 a2)  = [a] ++ flatten a1 ++ flatten a2 

class Sym a where
      sym :: a -> a -> Bool
	  
instance Eq a => Sym (BTplus a) where
		sym a b = (sym_ a b) && ((nub f) == f) 
			where f = flatten a
		
sym_ :: BTplus a -> BTplus b -> Bool		
sym_ Nil Nil = True
sym_ _ Nil = False
sym_ Nil _ = False
sym_ (Node _ a1 a2) (Node _ b1 b2) = (sym_ a1 b1) && (sym_ a2 b2)

Aufgabe 5

(5+15%) Definieren Sie filtert, das zwei Argumente erwartet: Eine einstellige boolsche Funktion und einen BTplus. Die Funktion liefere eine Liste jener Unterbäume zurück, auf die die boolsche Funktion zutrifft. Geben Sie auch hier eine möglichst allgemeine Deklaration an!

filtert :: (a -> Bool) -> BTplus a -> [BTplus a]
filtert f Nil = []
filtert f (Node a n1 n2)
	| f a = [(Node a n1 n2)] ++ filtert f n1 ++ filtert f n2
	| otherwise = filtert f n1 ++ filtert f n2

Kürzer (mit mehr syntactic sugar):

filtert :: (a -> Bool) -> BTplus a -> [BTplus a]
filtert _ Nil = []
filtert f n@(Node a t1 t2) = [n|f a] ++ filtert f t1 ++ filtert f t2