TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2013-03-01

Forum

Diskussion im Forum dazu: Thread

Aufgabe 1

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

mnr = [0,1,2,3,4,5,6]  :: [Int]
name = "Max Mustermann" :: String
kzn = "e53X" :: String


t1 = ("p1",(length.take 2)mnr, (take 2.(let no name = name;in no))"No"); -- irgendwie so

t2 = \x y z -> z.y.y

t3 = t2 (reverse) (\x->x++x++x) (take 4.drop 4)mnr 

t4 = ( [(i*2,i)|i<-mnr], [i>2|i<-mnr] ) -- irgendwie so

t5 = [[j|j<-[i..5]]|i<-mnr,i>1] -- irgendwie so

ml n l =[l!!i|i<-[5,n,4],i < length l];

t6=(ml 3 mnr,[(i,j)|i<-ml 3 mnr,j<- ml 3 mnr,i>j]);


p (e:t) = p t + e + p t
p _ = 0;

t7 = (p [mnr!!5, mnr!!6], p mnr)

Aufgabe 2

(5%) Definieren Sie einen polymorphen algebraischen Datentyp Bp zur Darstellung von binären Bäumen. Knoten enthalten zwei polymorphe Elemente und zwei Unterbäume. Weiters gibt es auch leere Bäume und leere Unterbäume.

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

Vorschlag von Martin:

data Bp a b = Nil | EmptyNode (Bp a b) (Bp a b) | Node a b (Bp a b) (Bp a b)

Aufgabe 3

(5%) Geben Sie einen konkreten Wert des Typs (Bp (Bp Integer Bool) (String), in Haskell-Syntax und als Zeichnung an.

tree :: Bp (Bp Integer Bool ) (String)
tree = Node (Node 1 True (Node 2 True (Nil) (Nil)) (Nil)) "ab" Nil Nil

Anderer Vorschlag

tree = (Node (Node 1 True Nil Nil) "Hi" (Node (Node 1 True Nil Nil) "Hi" Nil Nil) Nil)

Aufgabe 4

(5+15%) Definieren Sie erq. das für zwei Bäume des Typs Bp genau dann True ist, wenn sie die gleiche Knotenstruktur besitzen und die ersten Elemente des ersten Baums gleich der zweiten elemente des zweiten Baums sind.

Vorschlag (Ausgebessert lt. Diskussion Informatik Forum):

erq :: Eq a => (Bp a b) -> (Bp c a) -> Bool
erq Nil Nil = True
erq _ Nil = False
erq Nil _ = False
erq (Node a b t1 t2) (Node c d t3 t4) = and [erq t1 t3, erq t2 t4, a == d]

Aufgabe 5

(5+15%) Definieren Sie filterb, das zwei Argumente erwartet: Eine einstellige boolsche Funktion und einen Bp. Die Funktion liefere eine Liste der ersten Elemente jener Knoten zurück, auf deren zweiten Elemente die boolsche Funktion zutrifft. Geben Sie auch hier eine möglichst allgemeine Deklaration an!

Vorschlag:

filterb :: (b -> Bool) -> Bp a b -> [a]
filterb f Nil = []
filterb f (Node a b t1 t2) = (if f b then [a] else []) ++ filterb f t1 ++ filterb f t2

Vorschlag mit List comprehension:

filterb :: (b -> Bool) -> Bp a b -> [a]
filterb func Nil = []
filterb func (Node va vb l r)
	= [i | i <- [va], (func vb) == True] ++ (filterb func l) ++ (filterb func r)

Vorschlag mit List comprehension noch kürzer:

filterb :: (b -> Bool) -> Bp a b -> [a]
filterb _ Nil = []
filterb func (Node va vb l r)
	= [va | func vb] ++ filterb func l ++ filterb func r