TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2014-01-16

Ziemlich exakt die gleiche Prüfung wie Prüfung 2016-01-14.

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

Geben Sie die Werte und den allgemeinsten Typ von t1 bis t7 an.

t1 = ("p1", (drop 9.show) mnr, (head.words.(let no n = name; in no))"No");

t2 = (\x y z a -> ((x.y)z, (y.x)z));

t3 = t2 reverse (take 3) mnr (drop 3);

t4 = ((drop 4) [[i-2]|i<-mnr], [i|i<-mnr, i>3]);

t5 = take 4 [[i|j<-[i..5]]|i<-mnr];

ml = (tail.tail.reverse.tail);
t6 = (ml mnr, take 5 [(i,j)|i<-ml mnr, j<-ml mnr, j>=i]);

p o (a:l) (b:m) n = o a b : p o l m n;
p o _ _ n = n;
t7 = p (+) (reverse mnr) mnr [11];

Aufgabe 2

Definieren Sie einen polymorphen algebraischen Datentyp BTplus zur Darstellung von Binärbäumen. Jeder Knoten enthält zwei unabhängige polymorphe Elemente sowie zwei Unterbäume. Ein Baum kann auch leer sein.

data BTPlus a b = Node a b (BTPlus a b) (BTPlus a b) | Nil deriving Show

Aufgabe 3

Geben Sie einen konkreten BTplus Baum an, der die Werte "a" und 2 enthält und genau zwei Knoten hat. Geben Sie auch den Typ des Baums an.

tree :: BTPlus [Char] Integer 
tree = Node "a" 1 (Node "b" 2 Nil Nil) Nil

Aufgabe 4

Zwei Bäume sollen verglichen werden wobei die Struktur übereinstimmen muss und für jeden Knoten das erste Element des ersten Baums dem zweiten Element des zweiten Baums entsprechen muss.

Wenn die beiden Bäume übereinstimmten, soll True zurückgegeben werden, sonst False.

vergleiche :: (Eq a) => (Eq b) => (BTPlus a b) -> (BTPlus a b) -> Bool
vergleiche Nil Nil = True
vergleiche _ Nil = False
vergleiche Nil _ = False
vergleiche (Node a1 b1 t1 t2) (Node a2 b2 t3 t4) = and [a1 == a2, b1 == b2, vergleiche t1 t3, vergleiche t2 t4]

Anmerkung: so wie es im Moment dasteht ist entweder die Implementierung falsch oder die Angabe...

In meiner Lösung vergleiche ich immer nur das erste Element vom ersten Baum mit dem zweiten Element vom zweiten Baum (wie es in der Angabe steht), daher brauche ich das Eq b nicht. Zum Testen hatte ich leider keine Zeit, aber vielleicht mag ja wer später kommentieren bzw. ausbessern.

comp :: Eq a => BTplus a b -> BTplus b a -> Bool
comp Nil Nil                             = True
comp (Node a1 _ l1 r1) (Node _ a2 l2 r2) = a1 == a2 && comp l1 r2 && comp r1 l2
comp _ _                                 = False

Aufgabe 5

Die Funktion filterbt soll eine einstellige Boolsche funktion sowie zwei BTplus Bäume als Parameter akzeptieren und eine Liste der Elemente beider Bäume zurückgeben, bei denen die Boolsche-Funktion True liefert. Wobei im ersten Baum nur die ersten Elemente des Knotens (Node x _ _ _ _) und im zweiten Baum nur die Elemente des zweiten Knotens (Node _ y _ _ _) geprüft und in die Liste aufgenommen werden sollen.

Da hier in einer Ergebnisliste die ersten Elemente des ersten Baums und die zweiten Elemente des zweiten Baums aufgenommen werden sollen, gehe ich davon aus dass beide Elemente den gleichen Typ haben müssen.

filterbt :: (a -> Bool) -> BTplus a a -> BTplus a a -> [a]
filterbt _ Nil Nil                           = []
filterbt _ _ Nil                             = []
filterbt _ Nil _                             = []
filterbt f (Node a _ l1 r1) (Node _ b l2 r2) = [a | f a] ++ [b | f b] ++ filterbt f l1 l2 ++ filterbt f r1 r2

Habe den obigen Code oben mittels HLint vereinfacht und man sieht, dass wenn ein Baum Nil ist, wird der andere Baum ignoriert. Ich denke die Lösung von TU_Wien:Funktionale_Programmierung_VU_(Knoop)/Prüfung_2016-01-14#Aufgabe_5 müsste stimmen. So ist die Funktion auch allgemeiner, da ja nur immer das erste bzw. zweite Element relevant ist und daher vom Typ a sein muss.

filterbt :: (a -> Bool) -> BTplus a b -> BTplus c a -> [a]
filterbt _ Nil Nil              = []
filterbt f (Node a _ t1 t2) Nil = [a | f a] ++ filterbt f t1 Nil ++ filterbt f t2 Nil
filterbt f Nil (Node _ b t1 t2) = [b | f b] ++ filterbt f Nil t1 ++ filterbt f Nil t2
filterbt f t1 t2                = filterbt f t1 Nil ++ filterbt f Nil t2