TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2013-04-26

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

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

mnr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] {- Matrikelnummer -}
name = "Mustermann Max"             {- Name -}
knz = "E 033 534"                   {- Studienkennzahl -}

t1 = ("p1",(length.words)name, (take 3 .(let no name= name; in no))"NO");
{- ("p1",2,"NO") :: ([Char],Integer,[Char]) -}

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

t3 = t2 (take 3 . reverse) mnr mnr
{- ([7,6,5],[5,6,7]) :: ([Integer],[Integer]) -}

t4 = (( take 4 . drop 2) [[i-2]|i<-mnr], take 3 [i|i<-mnr,i<3] );
{- ([[1],[2],[3],[4]],[1,2]) :: ([[Integer]],[Integer]) -}

t5 = take 4 [[j|j<-[5..i]]|i<-mnr];
{- [[],[],[],[]] :: [[Integer]] -}

ml n = (take 5 . reverse . drop n);
t6 = (ml 3 mnr, [(i,j)|j<- ml 3 mnr, i<- ml 3 mnr, i<j] );
{- ([7,6,5,4],[(6,7),(5,7),(4,7),(5,6),(4,6),(4,5)]) :: ([Integer],[(Integer,Integer)]) -}

p (a:b:l) | a <= b = p (b:l);
p (a:l) = p l + a + p l;
p _ = 1;
t7 = ( (p.drop 4)mnr , p mnr);
{- (9,9) :: (Integer,Integer) -}

Aufgabe 2

Definieren Sie einen polymorphen algebraischen Datentyp BTree zur Darstellung von binären Bäumen mit Knoten und Blättern. Knoten enthalten nur zwei Unterbäume. In den Blättern finden sich zwei (unabhängige) polymorphe Elemente (erster und zweiter Eintrag). Es gibt auch leere Bäume und Unterbäume.

data BTree a b = Nil |
                 Node (BTree a b) (BTree a b) |
                 Leaf a b

Aufgabe 3

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

tree = Leaf (Leaf 1 True) "ab"

Aufgabe 4

Definieren Sie beq, das für zwei BTree-Bäume genau dann True ist, wenn sie die gleiche Knotenstruktur besitzen und die zweiten Elemente der Knoten des ersten Baums alle gleich dem ersten Element im entsprechenden Knoten des zweiten Baums sind. Geben Sie für beq die entsprechende Typedeklaration an.

beq :: Eq b => BTree a b -> BTree b c -> Bool
beq (Node t1a t1b) (Node t2a t2b) = beq t1a t2a && beq t1b t2b
beq (Leaf _ b) (Leaf a _) = a == b
beq Nil Nil = True
beq _ _ = False

2. Zeile stimmt nicht (EDIT: "beq t1b t2a && beq t1a t2b" wurde ausgebessert(EDIT: War wieder nicht richtig))

Aufgabe 5

Definieren Sie filterbt, das eine einstellige boolsche Funktion und zwei BTree erwartet und eine Liste jener zweiten Einträge des ersten Baums und jener ersten Einträge des zweiten Baums in beliebiger Reihenfolge zurückliefert, für die die boolsche Funktion zutrifft. Geben Sie für filterbt die entsprechende möglichst allgemeine Typdeklaration an.

filterbt :: (a -> Bool) -> (BTree b a) -> (BTree a c) -> [a]
filterbt _ Nil Nil = []
filterbt f (Leaf _ b) t2 = [b|f b] ++ filterbt f Nil t2
filterbt f t1 (Leaf a _) = [a|f a] ++ filterbt f t1 Nil
filterbt f (Node t1a t1b) t2 = (filterbt f t1a Nil) ++ (filterbt f t1b Nil) ++ (filterbt f Nil t2)
filterbt f t1 (Node t2a t2b) = (filterbt f Nil t2a) ++ (filterbt f Nil t2b) ++ (filterbt f t1 Nil)