TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2016-01-14

Ziemlich exakt die gleiche Prüfung wie Prüfung 2014-01-16.

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

Geben Sie die Werte und den allgemeinsten Typ von t1 bis t7 an. (Hier im VoWi kannst du die leeren Zeilen auswählen um die Lösungen zu sehen.)

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

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

{- t1 == ["p1","5,6,7]","Mustermann"] :: [[Char]] -}

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

{- t2 :: (a -> a) -> (a -> a) -> a -> b -> (a,a) -}

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

{- t3 == ([3,2,1], [7,6,5]) :: ([Integer],[Integer]) -}

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

{- t4 == ([[3],[4],[5]], [4,5,6,7]) :: ([[Integer]], [Integer]) -}

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

{- t5 == [[1,1,1,1,1], [2,2,2,2], [3,3,3], [4,4]] :: [[Integer]] -}

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

{- t6 == ([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]

{- t7 == [8,8,8,8,8,8,8,11] :: [Integer] -}

Aufgabe 2

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

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

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

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