Systematisches Programmieren Sommersemester 2020
Dr. Maurice Chandoo Leibniz Universität Hannover

AB2 Rekursive Ausdrücke

Implementieren Sie die folgenden Funktionen nur unter Verwendung der bereits importierten Funktionen. Folgende Sprachkonstrukte dürfen nicht verwendet werden:

• if ... then ... else ... (benutzen Sie stattdessen if' sofern importiert)
• Guards
• List Comprehensions: [(i,j) | i <- [1,2], j <- [3,4]]

Arithmetic Sequences [i .. j] sind nun erlaubt und an einigen Stellen auch notwendig (entspricht der Funktion listFromTo).

🎦 Selbstreduktion (klicken, um Video anzuschauen) 🎦

Die nachfolgenden Probleme können alle durch Selbstreduktion gelöst werden. Bei dieser algorithmischen Technik wird ein Problem gelöst, indem eine Instanz (Eingabe) mithilfe einer Reduktionsregel in eine (manchmal auch mehrere) kleinere Instanz umgewandelt wird, für welche rekursiv eine Lösung berechnet wird. Aus der Lösung der kleineren Instanz wird dann die Lösung für die ursprüngliche Instanz berechnet. Instanzen, auf welche die Reduktionsregel nicht angewendet wird, nennen wir irreduzibel. Für solche Instanzen gibt es einen separaten Teil im Algorithmus, welcher die Lösung berechnet.

Teil 1: Primitive Sort

Eine Liste ist (aufsteigend) sortiert gdw. für alle benachbarten Elemente der Liste gilt, dass das linke Element nicht größer ist als das rechte. Wir bezeichnen zwei benachbarte Elemente in einer Liste als u-Zeugen (u = unsortiert), falls das linke Element größer ist als das rechte. Das heißt, eine Liste ist sortiert gdw. sie keine u-Zeugen enthält. Ist eine Liste unsortiert, können wir den ersten u-Zeugen nehmen und die beiden Elemente vertauschen. Wiederholt man dies ausreichend oft, dann ist die Liste sortiert. Dieser Algorithmus kann als eine Vorstufe von BubbleSort betrachtet werden. Die Funktion unorderedWitnesses gibt die Liste der u-Zeugen von arg1 zurück. Ein u-Zeuge wird dabei durch den Index des linken Elements beschrieben. Beispiele:

• unorderedWitnesses [2,1,4,7,0] = [0,3]
• unorderedWitnesses [1,2,3,4] = []

Die Funktion swap vertauscht die Elemente mit Index arg1 und arg2 in arg3.
Die Funktion primitiveSort gibt arg1 in aufsteigend sortierter Reihenfolge zurück. Die Funktion soll durch den obigen Algorithmus implementiert werden.

Teil 2: Arithmetik

Für diesen Teil können Sie davon ausgehen, dass alle Eingabeparameter ≥ 0 sind. Die Funktion pow ist definiert als arg1 ^ arg2. Die Funktion genericArithmetic soll so definiert werden, dass folgende Spezifikation gilt ('?' müssen passend ersetzt werden):

Teil 3: Azyklische Graphen

Ein gerichteter Graph \(G\) ist azyklisch gdw. er keine Knoten enthält oder wenn seine reduzierte Form \(G'\) azyklisch ist. Den Graph \(G'\) erhält man, indem alle Knoten aus \(G\) gelöscht werden, welche nicht mindestens einen eingehenden und einen ausgehenden Nachbarn haben. Solche Knoten können nicht Teil eines Zyklus sein.
Im obigen Graph ist 2 ein ausgehender Nachbar von 1 und 3 ein eingehender Nachbar von 1. Dieser Graph wird in Code wie folgt ausgedrückt: Graph [(1,[2]),(2,[3]),(3,[1])]. Ein Graph ist codiert als Liste von Tupeln, wobei der erste Teil den Knoten enthält und der zweite die Liste der ausgehenden Nachbarn dieses Knotens. Sie können davon ausgehen, dass die Listen der ausgehenden Knoten keine Duplikate enthalten und jeder ausgehende Nachbar auch als Knoten im Graphen existiert.
Die Funktion isEmptyGraph ist wahr gdw. der Graph keine Knoten enthält.
Die Funktion vertices gibt die Liste aller Knoten eines Graphen zurück.
Die Funktion inNeighbors gibt die eingehenden Nachbarn von Knoten arg1 in Graph arg2 zurück.
Die Funktion outNeighbors gibt die ausgehenden Nachbarn von Knoten arg1 in Graph arg2 zurück.
Die Funktion reduction gibt die reduzierte Form \(G'\) eines Graphen \(G\) zurück.
Die Funktion acyclic gibt wahr zurück gdw. der Graph azyklisch ist. Die Funktion soll durch die obige Reduktionsregel implementiert werden.

Teil 4: Teilmengen

Die Menge aller nicht-leeren Teilmengen einer Menge \(M\) besteht aus \(M\) (sofern \(M\) selbst nicht die leere Menge ist) und der Menge aller nicht-leeren Teilmengen von \(M_1, M_2, \dots, M_n\) wobei \(n = |M|\) und \(M_i\) gleich der Menge \(M\) ohne das \(i\)-te Element ist. Die Funktion subsets gibt eine Liste zurück, welche jede nicht-leere Teilmenge von arg1 enthält (Duplikate sind erlaubt und die Reihenfolge kann beliebig sein). Falls arg1 die leere Liste ist, dann ist der Rückgabewert von subsets auch die leere Liste. Sie können davon ausgehen, dass arg1 kein Element doppelt enthält. Die Funktion soll durch die obige Reduktionsregel implementiert werden.
Die Funktion kSubsets gibt eine Liste zurück, welche alle Teilmengen von arg2 mit arg1 Elementen enthält (ohne Duplikate, Reihenfolge beliebig). Sie dürfen annehmen, dass arg1 ≥ 1.

Teil 5: Erfüllbarkeit & Tautologien

Eine \(k\)-stellige boolesche Funktion \(f\) ist erfüllbar gdw. \(f_0\) oder \(f_1\) erfüllbar ist, wobei \(k \geq 1\) und \(f_i\) die \((k-1)\)-stellige Funktion ist, welche aus \(f\) hervorgeht, wenn der erste Parameter auf \(i\) festgelegt wird. Eine boolesche Funktion beliebiger Arität ist als BooleanFunction codiert. Die Funktion partialApply legt den ersten Parameter der Funktion arg2 auf arg1 fest (die festgelegten Parameter werden im zweiten Argument vom Konstruktor BooleanFunction gespeichert); die Arität der zurückgegebene boolesche Funktion verringert sich entsprechend um eins. Die Funktion eval wertet arg2 für die Belegung arg1 aus; die Länge von arg1 muss gleich der Arität von arg2 sein. Die Funktion arity gibt die Arität der booleschen Funktion arg1 zurück.

Beispiel

exampleFormula = (BooleanFunction f [] 3) 
  where
    f [x1,x2,x3] = (not x1) && (x2 || x3) 
   
eval [True,False,False] exampleFormula -- False
eval [False,True,False] exampleFormula -- True

Die Funktion sat gibt wahr zurück gdw. die boolesche Funktion mindestens eine erfüllende Belegung besitzt. Die Funktion soll durch die obige Reduktionsregel implementiert werden.
Die Funktion taut gibt wahr zurück gdw. jede Belegung die boolesche Funktion erfüllt.