TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2018-01-18

Es ist bis auf das tail in Aufgabe1 sehr ähnlich zu den Prüfungen Prüfung 2016-01-14 und Prüfung 2014-01-16

Aufgabe 1 (50%)

Geben Sie die Wert und den 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 = "E 033 4711" -- Studienkennzahl - falls mehrere Studien

t1 = ["p1", (drop 9.show)mnr, (head.words.(let no n=name;in no))"No"]
{- ["p1","5,6,7]","Mustermann,"] :: [[Char]]-}

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

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

t4 = ( drop 4 [[i-2]|i<-mnr], take 3 [i|i<-mnr,i>3])
{- ([[3],[4],[5]],[4,5,6]) :: ([[Integer]],[Integer]) -}

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

ml _ = (tail.tail.reverse.tail)
t6 = ( ml 1 mnr, take 5[(i,j)|i<- ml 2 mnr,j<-ml 3 mnr, j>=i ])
{- ([5,4,3,2],[(5,5),(4,5),(4,4),(3,5),(3,4)]) :: ([Integer],[(Integer,Integer)]) -}

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]
{- [8,8,8,8,8,8,8,11] :: [Integer] -}

Aufgabe 2 (5%)

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

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

Aufgabe 3 (5%)

Geben Sie einen konkreten Wert für BTplus sowie seinen genauen Typ an, der die Werte "a" und 2 enthält und genau zwei Knoten aufweist, in Haskell-Syntax mit seinem Typ und als Zeichnung.

tree1 = Node "a" 2 (Node "b" 3 Nil Nil) Nil :: BTPlus [Char] Integer

Aufgabe 4 (10%+10%)

Definieren Sie requal, das für zwei BTplus-Bäume genau dann True ist, wenn beide Bäume Knoten an den gleichen Stellen besitzen und der zweite polymorphe Eintrag jedes Knotens gleich dem ersten Eintrag des anderen an der gleichen Stelle befindlichen Knotens ist. Geben Sie hier eine möglichst allgemeine Deklaration an!

requal :: (Eq a, Eq b) => BTPlus a b -> BTPlus b a -> Bool
requal Nil Nil                           = True
requal (Node a b t1 t2) (Node c d t3 t4) = (a == d) && (b == c) && requal t1 t3 && requal t2 t4
requal _ _                               = False

Aufgabe 5 (5+15%)

Definieren Sie filterbt, das eine einstellige boolsche Funktion und zwei BTplus erwartet und eine Liste jener ersten Einträge des ersten Baums und jener zweiten 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) -> 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