Systematic Programming Summer Semester 2020
Dr. Maurice Chandoo Leibniz Universität Hannover

AB2 Recursive Expressions

Implement the following functions using only the already imported functions. Additionally, the following language constructs are not permitted:

• if ... then ... else ... (use if' instead if imported)
• Guards
• List Comprehensions: [(i,j) | i <- [1,2], j <- [3,4]]

Arithmetic Sequences [i .. j] are now allowed and, in fact, required for certain cases (they are equivalent to listFromTo).

🎦 Self-Reduction (click to watch video) 🎦

The following problems can all be solved using self-reduction. For this algorithmic technique a problem is solved by converting an instance (input) into a smaller one (sometimes multiple smaller instances) using a reduction rule. The solution for this smaller instance is computed recursively. Using the solution of the smaller instance, the solution of the original instance is computed. Instances to which the reduction rule cannot be applied are called irreducible. For these instances there is a separate part in the algorithm which computes the solution.

Part 1: Primitive Sort

A list is sorted (in ascending order) iff for all neighboring elements of the list it holds that the left element is not larger than the right. We call two neighboring elements u-witness (u = unsorted) if the left element is larger than the right one. Thus, a list is sorted iff it contains no u-witnesses. If a list is unsorted then we can take the first u-witness and swap the two elements. If this is repeated sufficiently often then the list will be sorted eventually. This algorithm can be regarded as a primitive variant of BubbleSort. The function unorderedWitnesses returns the list of u-witnesses of arg1. A u-witness is encoded as the index of its left element. Examples:

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

The function swap swaps the elements at index arg1 and arg2 in arg3.
The function primitiveSort returns arg1 sorted in ascending order. The function should be implemented using the algorithm described above.

Part 2: Arithmetic

For this part you may assume that all input parameters are larger or equal 0. The function pow is defined as arg1 ^ arg2. The function genericArithmetic should be implemented such that the following specification holds ('?' have to be replaced adequately):

Part 3: Acyclic Graphs

A directed graph \(G\) is acyclic iff it contains no vertices or if its reduced form \(G'\) is acyclic. The graph \(G'\) can be obtained by deleting all vertices from \(G\) which do not have at least one out-neighbor and one in-neighbor. Such vertices cannot be part of a cycle.
In the above graph 2 is an out-neighbor of 1 and 3 is an in-neighbor of 1. This graph can be expressed as Graph [(1,[2]),(2,[3]),(3,[1])] in code. A graph is encoded as list of tuples. The first part of the tuple is the vertex and the second is the list of its out-neighbors. You may assume that the list of out-neighbors does not contain duplicates and that every vertex that occurs in some list of out-neighbors also occurs in the first part of some tuple.
The function isEmptyGraph returns true iff the graph contains no vertices.
The function vertices returns the list of all vertices of a graph.
The function inNeighbors returns the list of in-neighbors of the vertex arg1 in graph arg2.
The function outNeighbors returns the list of out-neighbors of vertex arg1 in graph arg2.
The function reduction returns the reduced form \(G'\) of a graph \(G\).
The function acyclic returns true iff the given graph is acyclic. The function should be implemented using the above reduction rule.

Part 4: Subsets

The set of all non-empty subsets of a set \(M\) consists of \(M\) (assuming \(M\) is not the empty set) and the set of all non-empty subsets of \(M_1, M_2, \dots, M_n\) where \(n = |M|\) and \(M_i\) equals the set \(M\) without the \(i\)-th element. The function subsets returns a list which contains every non-empty subset of arg1 (duplicates are allowed and the order can be arbitrary). If arg1 is the empty list then the return value should be the empty list as well. You may assume that arg1 contains no duplicates. The function should be implemented using the above reduction rule.
The function kSubsets returns the list which contains all subsets of arg2 with arg1 ≥ 1 elements (there should be no duplicates and the order may be arbitrary). You may assume that arg1 ≥ 1.

Part 5: Satisfiability & Tautologies

A \(k\)-ary Boolean function \(f\) is satisfiable iff \(f_0\) or \(f_1\) is satisfiable with \(k \geq 1\) and \(f_i\) is the \((k-1)\)-ary function which results from \(f\) by setting the first input parameter to \(i\). A Boolean function of arbitrary arity is encoded as BooleanFunction. The function partialApply sets the first input parameter of the function arg2 to arg1 (the set input parameters are stored in the second argument of the constructor BooleanFunction); the arity of the returned Boolean function decreases by one. The function eval evaluates arg2 for the assignment arg1; the length of arg1 has to match the arity of arg2. The function arity returns the arity of the Boolean function arg1.

Example

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

The function sat returns true iff the Boolean function has at least one satisfying assignment. The function should be implemented using the above reduction rule.
The function taut returns true iff every assignment satisfies the Boolean function.