TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2008-01-24

Aus VoWi
Wechseln zu: Navigation, Suche

Insgesammt gab es auf eine Pruefung 50 Punkte.

Gruppe A[Bearbeiten]

Die Fragen sind nicht im Wortlaut wiedergegeben, die Aufgaben prinzipiell sollten aber korrekt sein.

Aufgabe 1 (5 Punkte)[Bearbeiten]

a) (4 Punkte) 
Implementiere eine rekursive Funktion sumEven n, die die Summe der ersten n geraden Zahlen zurueckliefert: sumEven = \sum_{i=0}^n 2*i
sumeven :: Int -> Int
sumeven n | (n > 0)  = (2*n) + (sumeven(n-1))
          | otherwise = 0
b) (1 Punkt) 
Welchen Rekursionstyp haben Sie in der von Ihnen implementierten Methode angewandt.

Lineare Rekursion

Aufgabe 2 (4 Punkte)[Bearbeiten]

Gegeben sei folgende Funktionsimplementation:

f (x:xs) (y:ys) = (x,y) : (f xs ys )
f _ []          = []
f [] _          = []

Finden Sie die Typsignatur von f.


[a] -> [b] -> [(a,b)]

Aufgabe 3 (15 Punkte)[Bearbeiten]

Gegeben ist folgende funktion:

fun f xs p = [ p (f x) | x <- xs ]
a) (4 Punkte) 
Geben sie die Typsignatur von fun an
b) (1 Punkte) 
Wie nennt man das Konstrukt "[ p (f x) | x <- xs ]"?
c) (6 Punkte) 
Implementieren sie die Funktion fun mittels der Funktionen map und filter.
d) (4 Punkte) 
Gegeben ist der Ausdruck:
fun f1 [1,2,3,4,5] f2
Geben Sie eine Typsignatur und eine Implementation der Funktionen f1 und f2 an, sodass der obige Ausdruck korrekt wird.

Aufgabe 4 (5 Punkte)[Bearbeiten]

Gegeben ist folgender Datentyp:

data Tree = Leaf Int |
            Node Int Tree Tree

Machen sie Tree eine Instanz von Eq und implementieren Sie (==)

Lösung:

instance Eq Tree where
	(==) (Leaf n) (Leaf m) = n==m
	(==) (Node x t1 t2) (Node y t3 t4) = (x==y) && (t1==t3) && (t2==t4) 
	(==) (Leaf _) (Node _ _ _) = False
	(==) (Node _ _ _) (Leaf _) = False

Aufgabe 5 (8 Punkte)[Bearbeiten]

Gegeben ist folgende Funktion:

f (3+5) * f (2+3)

f :: Integer -> Integer
f n = if (n>0) then f (n-1) + n else 0

Geben sie den jeweils naechsten Schritt bei

a) (4 Punkte) 
leftmost, outermost Auswertung
b) (4 Punkte) 
leftmost, innermost Auswertung

an.

Aufgabe 6 (3 Punkte)[Bearbeiten]

Ist der Ausdruck

type Tree a b = Leaf a |
       Node b (Tree a b) (Tree a b)

syntaktisch korrekt?

Aufgabe 7 (5 Punkte)[Bearbeiten]

Warum ist intuitiv berechenbar \equiv \lambda-Kalkuel? Und warum ist der Zusammenhang nicht beweisbar?

Aufgabe 8 (5 Punkte)[Bearbeiten]

Beschreiben sie den Zusammenhang zwischen intuitiver Berechenbarkeit, \lambda-Kalkuel und Church-These.