TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2014-03-07

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

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

mnr = [0,2,0,0,3,3,1] :: [Integer]; {- Matrikelnummer -}
name = "Smith John" :: String; {- Familienname, Vorname(n) -}
knz = "999" :: String; {- Kennzahl -}

t1 = (take 2 . words . reverse . \x -> name++x)"!"

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

t3 = t2 (take 4) reverse (\x->x++[0]) mnr;

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

t5 = drop 3 [[j|j<-[i..3]]|i<-mnr];

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

p (a:b:l) | a <= b = p (b:l);
p (a:l) = p l + a + p l;
p [e] = 10000;
p [] = 0;
t7 = ( (p.drop 4)mnr , p mnr);

Aufgabe 2

5% Definieren Sie einen polymorphen algebraischen Datentyp TTree zur Darstellung von ternären Bäumen. Knoten enthalten drei unabhängige polymorphe Elemente und drei Unterbäume. Es gibt auch leere Bäume und Unterbäume.

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

Aufgabe 3

5% Geben Sie einen konkreten TTree-Baum in Haskell-Syntax mit seinem genauen Typ und als Zeichnung an, der die Werte "a" und 2 sowie einen TTree-Baum als Element enthält.

tree = Node "a" 2 Nil Nil Nil Nil
tree :: TTree [Char] Integer (TTree a b c)

Aufgabe 4

5+15%
Definieren Sie rrt, das für einen TTree-Baum genau dann True ist, wenn

1. alle ersten Elemente aller Knoten des rtt-Baums, wiederum einen TTree-Baum genannt Elementbaum enthalten, sowie
2. alle Elementbäume Knoten und leere Unterbäume aufweisen, und
3. das zweite und dritte Element aller Elementbäume gleich dem entsprechenden dritten und zweiten Element des rtt-Baums ist.

Geben Sie hier auch eine möglichst allgemeine Typdeklaration für rtt an!

rrt :: (Eq b, Eq c) => TTree (TTree a b c) c b -> Bool
rrt (Node (Node _ b' c' Nil Nil Nil) b c t1 t2 t3) = b' == c && c' == b && rrt t1 && rrt t2 && rrt t3
rrt Nil = True
rrt _   = False

Anmerkung:

Ich denke die Lösung darüber ist nicht korrekt, da b' mit c und c' mit b verglichen wird und diese nicht verglichen werden können, da sie unterschiedliche Typen sind. Je nach dem wie die Frage gemeint ist, müssten b' und c entweder den selben Typ haben oder es muss b' mit b und c' mit c verglichen werden.

Meine Lösung:

rrt :: (Eq b , Eq c) => TTree (TTree a b c) b c -> Bool
rrt (Node (Node _ b' c' Nil Nil Nil) b c n1 n2 n3) = (b' == b) && (c' == c) && (rrt n1) && (rrt n2) && (rrt n3)
rrt Nil = True
rrt _ = False

Die erste Lösung stimmt

Aufgabe 5

5+15%
Definieren Sie filtertt, das eine zweistellige boolsche Funktion und einen TTree erwartet und eine Liste jener Knoten in beliebiger Reihenfolge zurückliefert, bei denen die Funktion für den ersten und zweiten Eintrag True ist.

Geben Sie auch hier eine möglichst allgemeine Typdeklaration für filtertt an!

filtertt :: (a -> b -> Bool) -> TTree a b c -> [TTree a b c]
filtertt f n@(Node a b c t1 t2 t3) = [n|f a b] ++ filtertt f t1 ++ filtertt f t2 ++ filtertt f t3
filtertt _ Nil = []