TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2018-03-02

Aus VoWi
Zur Navigation springen Zur Suche springen

Die Prüfung ist sehr ähnlich zur Prüfung Prüfung 2017-01-19

Aufgabe 1 (50%)[Bearbeiten | Quelltext bearbeiten]

Geben Sie Wert und allgemeinsten Typ für t1 bis t7 an! (Hier im VoWi kannst du die leeren Zeilen auswählen um die Lösungen zu sehen.)

mnr = tail [0,1,2,3,4,5,6,7] :: [Integer]; {- Matrikelnummer -}
name = "Mustermann, Max" :: String; {- Familienname, Vorname(n) -}
knz = "E033 534" :: String {- Kennzahl -}

t1 = ("p1", (take 2.reverse.show)mnr, (head.words.(\n o ->o:name)'-')'+');
{- ("p1","]7","+Mustermann,") -}

t2 = (\x y z -> y.x.y); -- Hier nur allgemeinster Typ!
{- (a -> b) -> (b -> a) -> c -> b -> a -}

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

t4 = ( [i|i<-mnr, i>3], [(i, i`mod`3)|i<-mnr] );
{- ([4,5,6,7],[(1,1),(2,2),(3,0),(4,1),(5,2),(6,0),(7,1)]) -}

t5 = [(sum([i..4]),i)|i<-(tail mnr)];
{- [(9,2),(7,3),(4,4),(0,5),(0,6),(0,7)] -}

tls xs = xs: case xs of _:ys -> tls ys; _ -> [];
t6 = ((tls.take 3)mnr, take 5[j|1:j:_<-tls mnr]);
{- ([[1,2,3],[2,3],[3],[]],[2]) -}

p (a:l) = a + p l + a + p l;
p (a:b:l) | a <= b = p (b:l);
p [e] = 200000;
p _ = 0;
t7 = ( (p.drop 4)mnr, p mnr);
{- (90,1538) -}

Aufgabe 2 (5%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie einen polymorphen algebraischen Datentyp BTree 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 BTree a = Node a (BTree a) (BTree a) | Nil

Aufgabe 3 (5%)[Bearbeiten | Quelltext bearbeiten]

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

Node (Node 1 (Node 2 Nil Nil) Nil, "ab") Nil Nil :: BTree (BTree Integer, String)

Aufgabe 4 (5+15%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie juniq, das für einen Baum des Typs BTree genau dann True ist, wenn in jedem Knoten das polymorphe Element höchstens einmal in den Unterbäumen des Knotens vorkommt. Geben Sie für juniq auch die entsprechende Typdeklaration an. (Typklasse!)

juniq :: Eq a => BTree a -> Bool
juniq Nil = True
juniq (Node a l r) = ((count a l) < 2) && ((count a r) < 2) && (juniq l) && (juniq r)

count :: Eq a => a -> BTree a -> Integer
count _ Nil = 0
count a (Node b l r) = (if a == b then 1 else 0) + (count a l) + (count a r)

Aufgabe 5 ((5+15)%)[Bearbeiten | Quelltext bearbeiten]

Definieren Sie trx, das zwei Argumente erwartet: Eine einstellige boolsche Funktion und einen BTree. Die Funktion liefere eine Liste aus Tripeln jener Knoten zurück, für die die Funktion zutrifft (angewandt auf den gesamten Knoten). Im Tripel ist das erste Element das Knotenelement, das zweite der linke und das dritte der rechte Unterbaum. Die Elemente der Liste kommen in beliebiger Reihenfolge vor. Geben Sie auch hier eine möglichst allgemeine Deklaration an!

Lösungsvorschlag: Dragobitch (Diskussion) 14:12, 23. Feb. 2017 (CET)

trx :: (BTree a -> Bool) -> BTree a -> [(a, BTree a, BTree a)]
trx _ Nil = []
trx f n@(Node a l r) = [(a,l,r)|f n] ++ (trx f l) ++ (trx f r)