TU Wien:Funktionale Programmierung VU (Knoop)/Prüfung 2020-06-08

Zum Überblick: die Aufgaben beschäftigen sich jeweils mit...

1. Code schreiben (+erklären), Sonderfallbehandlung
2. Theorie: Typklassen, Polymorphie
3. Code interpretieren + schreiben auf verschiedene Arten, Theorie: Rekursionstypen, Auswertungsordnung
4. Datentyp-Definition Baum, Eq-instance-Bildung
5. Theorie: curryfiziert vs uncurryfiziert
6. Code schreiben (+erklären), Sonderfallbehandlung

Aufgabe 1 (2+2+10+8 = 22 Punkte = 22%)

Angabe

Zwei Zeichenreihen haben Abstand $n$, $n\in \mathbb {N} _{0}$, gdw. die beiden Zeichenreihen sind von gleicher Länge und unterscheiden sich an genau $n$ Positionen voneinander.

1. Gibt es Fälle für die Berechnung des Abstandes von Zeichenreihen, die von der obigen Beschreibung nicht erfasst sind und eine besondere Behandlung erfordern? Wenn ja, welche?
2. Wie können etwaige besondere Fälle sinnvoll behandelt werden? Nennen Sie eine Methode dafür und wie genau Sie damit etwaige besondere Fälle hier behandeln.
3. Schreiben sie eine curryfizierte Haskell-Rechenvorschrift abs einschließlich ihrer syntaktischen Signatur, die angewendet auf zwei Zeichenreihen ihren Abstand liefert. Etwaige besondere Fälle sollen von abs so behandelt werden, wie in der vorigen Teilaufgabe beschrieben.
4. Erklären Sie knapp, aber gut nachvollziehbar, wie Ihre Rechenvorschrift vorgeht.

Aufgabe 2 (4+4+2+2+2 = 14 Punkte)

1. Wie sind Typklassen in Haskell aufgebaut?
2. Wozu dienen sie?
3. Mit welcher Art von Polymorphie sind Typklassen eng verbunden?
4. Was ermöglicht diese Art von Polymorphie wiederzuverwenden?
5. Welche synonymen Bezeichnungen gibt es für diese Polymorphieart?

Aufgabe 3 (2+1+(3*2)+5 = 14 Punkte)

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

1. Was berechnet f?
2. Von welchem Rekursionstyp ist f?
3. Schreiben Sie die Funktion f bedeutungsgleich
   1. mithilfe bewachter Ausdrücke.
   2. argumentfrei mithilfe einer anonymen lambda-Abstraktion.
   3. unter (Mit-) Verwendung einer Listenkomprehension.
4. Geben Sie die ersten 5 Schritte der Auswertung des Aufrufs f (2+3) entsprechend der Standard Auswertungsordnung von Haskell an:

Aufgabe 4 ((2*4)+8 = 16 Punkte)

Angabe

Wir betrachten Bäume, deren Blätter eine Benennung und deren Nichtblätter zwei Benennungen tragen und keinen oder beliebig viele Teilbäume besitzen. Ein Wald von Bäumen enthält beliebig viele oder auch gar keinen Baum.

1. Geben Sie möglichst typallgemeine Definitionen für Bäume und Wälder in Haskell an. Verwenden Sie algebraische Datentypen nur, wenn nötig.
2. Machen Sie den Baumtyp zu einer Instanz der Typklasse Eq, ohne dafür eine deriving-Klausel zu verwenden. Zwei Bäume sind gleich gdw. die stimmen in Struktur und Benennugen überein.

Lösungsvorschlag

1. data Baum a b c = Blatt a | Knoten a b [Baum a b c] | Wald [Baum a b c]
   

2. instance (Eq a, Eq b, Eq c) => Eq (Baum a b c) where
   Blatt _ == Knoten _ _ _ = False
   Knoten _ _ _ == Blatt _ = False 
   Blatt a == Blatt b = a == b
   Knoten a b c == Knoten d e f = a == d && b == e && c == f
   

Aufgabe 5 (3+3 = 6 Punkte)

Was bedeutet die Signatur der Funktion h:

h :: (a -> b) -> [a] -> [b]

in

1. curryfizierter Lesart?
2. nicht-curryfizierter Lesart?

Aufgabe 6 (2+2+16+8 = 28 Punkte)

Eine Menge von Zeichenreihen hat Abstand n, n ∈ IN₀, gdw. die Menge ist nicht leer, alle Zeichenreihen der Menge sind von gleicher Länge, die Menge enthält zwei voneinander verschiedene Zeichenreihen mit Abstand n, die Menge enthält keine zwei verschiedenen Zeichenreihen mit Abstand m und m < n.

1. Gibt es Fälle für die Berechnung des Abstandes einer Menge von Zeichenreihen, die von der obigen Beschreibung nicht erfasst sind und eine besondere Behandlung erfordern? Wenn ja, welche?
2. Wie kännen etwaige besondere Fälle sinnvoll behandelt werden? Nennen Sie eine andere Methode als in Aufgabe 1 dafür und wie genau Sie damit etwaige besondere Fälle hier behandeln.
3. Schreiben Sie die Haskell-Rechenvorschrift mabs einschließlich ihrer syntaktischen Signatur, die angewendet auf eine Menge von Zeichenreihen ihren Abstand liefert. Die Menge ist dabei in Form einer Liste von Zeichenreihen gegeben. Etwaige besondere Fälle sollen von mabs so behandelt werden, wie in der vorigen Teilaufgabe beschrieben.
4. Erklären Sie knapp, aber gut nachvollziehbar, wie ihre Rechenvorschrift vorgeht.

Die Funktion abs aus Aufgabe 1 können Sie für Aufgabe 6 als gegeben voraussetzen.