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

Insgesammt gab es auf eine Pruefung 50 Punkte.

Gruppe A

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

Aufgabe 1 (5 Punkte)

a) (4 Punkte)

Implementiere eine rekursive Funktion sumEven n, die die Summe der ersten n geraden Zahlen zurueckliefert: sumEven = $\sum _{i=0}^{n}2\ast 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)

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)

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)

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)

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)

Ist der Ausdruck

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

syntaktisch korrekt?

Aufgabe 7 (5 Punkte)

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

Aufgabe 8 (5 Punkte)

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