TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2008-04-28

Insgesamt gab es 50 Punkte.

Gruppe B

Bsp 1 (4+1 Punkte)

Gegeben

data Tree = Leaf Integer |
Node Integer Tree Tree

1.1.: Schreibe Funktion isLabel, die überprüft, ob der Baum einen gewissen Integer enthält, wenn ja, true zurückgeben, wenn nein, false.

1.2.: Welcher Rekursionstyp wurde verwendet?

Bsp 2 (3+5 Punkte)

Gegeben

concat :: (String,String) -> String
concat (s,t) = s ++ t

2.1.: Was ist currifiziert/uncurryfiziert.

2.2.: Signatur von curry aufschreiben, curry auf concat anwenden mit Beispieleingabe und -output.

Bsp 3 (5 Punkte)

Man soll die kleinste Fakultät finden, die größer als eine bestimmte Zahl ist. Die Fakultätsfunktion ist gegeben. Es ist Listenkomprehension zu verwenden.

-- Fakutltätsfunktion

   fac :: Int -> Int
   fac 0 = 1
   fac n = n * fac (n-1)

-- Berechnung der kleinsten fakultät > n

   smallFac :: Int -> Int
   -- da die liste fuer 0 bis n erstellt wird gibt es die sonderfälle < 1, für alle zahlen < 1 ist die kleinste fakultät 1
   -- und da die fakultät von 1 = 1 und von 2 = 2 ist sind diese beiden auch sonderfälle und werden explizit behandelt
   smallFac n
       | n < 1 = 1
       | n == 1 = 2
       | n == 2 = 6
       | otherwise = fac ([x | x <- [0..n], (fac x) > n]!!0)

Ich kapier nicht ganz, was der Vorautor in seinem Kommentar zu smallFac meint. Meine Lösung sieht so aus:

   smallFac :: Int -> Int
   smallFac x = head [ (fac i) | i <- [0..], ((fac i) > x) ]

Ist getestet und geht.

Bsp 4 (4+4 Punkte?)

Gegeben

fun p h t x
    | p x = []
    | h x : fun p h t (t x)

(sic!)

es war ziemlich sicher das hier gemeint:

fun p h t x
| p x = []
| otherwise = h x : fun p h t (t x)

4.1.: Allgemeinste Typsignatur angeben.

4.2.: Ein Aufrufbeispiel mit Ausgabe, wobei das Ergebnis nicht nur von der ersten Zeile abhängen darf.

Hier war dann die Zeit aus, d.h. ich konnte die restlichen Beispiele nicht mehr aufschreiben, die sind daher aus dem Gedächtnis.

Bsp 5 (? Punkte)

Lambdakalkül: Wozu ist die Normalform da, was nutzt sie, einen Ausdruck in NF transferieren.

Bsp 6 (4+2+2 Punkte)

Man soll eine Datenstruktur für einen gerichteten Graphen entwickeln, wobei jeder Knoten mindestens eine ausgehende Kante haben muss. Dazu sind zwei Beispielgraphen gegeben.

6.1.: Typsichere Datenstruktur angeben.

6.2.: Datenstruktur erklären, erklären warum typsicher.

6.3.: Die beiden Beispielbäume aus der Angabe in der Datenstruktur angeben.

Bsp 7 (? Punkte)

Wieder Lambdakalkül. Wofür braucht man die Nebenbedingung bei der Alpha-Transformation, was passiert, wenn man sie wegläßt, Beispiel, was dann passiert.

Bsp 8 (? Punkte)

Erklären, was die Tatsache, dass die Ausdrücke

x+x
where x = (f a)

und

(f a) + (f a)

mit der referentiellen Transparenz zu tun haben und erklären, was referentielle Transparenz ist.