AB2 Recursive Expressions
Implement the following functions using only the already imported functions. Additionally, the following language constructs are not permitted:
[i .. j]
are now allowed and, in fact, required for certain cases (they are equivalent to
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.
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.
unorderedWitnesses :: (Ord a) => [a] -> [Int]
swap :: Int -> Int -> [a] -> [a]
primitiveSort :: (Ord a) => [a] -> [a]
returns the list of u-witnesses of
. 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] = 
swaps the elements at index
sorted in ascending order. The function should be implemented using the algorithm described above.
For this part you may assume that all input parameters are larger or equal 0.
add :: Int -> Int -> Int
mult :: Int -> Int -> Int
pow :: Int -> Int -> Int
is defined as
arg1 ^ arg2
genericArithmetic :: (Int -> Int) -> (Int -> Int -> Int) -> Int -> Int -> Int
should be implemented such that the following specification holds ('?' have to be replaced adequately):
add x y = (genericArithmetic id ?) x y
mult x y = (genericArithmetic ? add) x y
pow x y = (genericArithmetic ? ?) x y
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
type Vertex = Int
type OutNeighbors = [Vertex]
data Graph = Graph [(Vertex,OutNeighbors)] deriving (Eq, Show, Read)
isEmptyGraph :: Graph -> Bool
vertices :: Graph -> [Vertex]
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.
returns true iff the graph contains no vertices.
returns the list of all vertices of a graph.
inNeighbors :: Vertex -> Graph -> [Vertex]
outNeighbors :: Vertex -> Graph -> [Vertex]
reduction :: Graph -> Graph
acyclic :: Graph -> Bool
returns the list of in-neighbors of the vertex
returns the list of out-neighbors of vertex
returns the reduced form \(G'\) of a graph \(G\).
returns true iff the given graph is acyclic. The function should be implemented using the above reduction rule.
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.
subsets :: (Ord a) => [a] -> [[a]]
kSubsets :: (Ord a) => Int -> [a] -> [[a]]
returns a list which contains every non-empty subset of
(duplicates are allowed and the order can be arbitrary). If
is the empty list then the return value should be the empty list as well. You may assume that
contains no duplicates. The function should be implemented using the above reduction rule.
returns the list which contains all subsets of
≥ 1 elements (there should be no duplicates and the order may be arbitrary). You may assume that
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\).
data BooleanFunction = BooleanFunction ([Bool] -> Bool) [Bool] Arity
eval :: [Bool] -> BooleanFunction -> Bool
partialApply :: Bool -> BooleanFunction -> BooleanFunction
arity :: BooleanFunction -> Int
A Boolean function of arbitrary arity is encoded as
. The function
sets the first input parameter of the function
(the set input parameters are stored in the second argument of the constructor
); the arity of the returned Boolean function decreases by one. The function
for the assignment
; the length of
has to match the arity of
returns the arity of the Boolean function
exampleFormula = (BooleanFunction f  3)
f [x1,x2,x3] = (not x1) && (x2 || x3)
eval [True,False,False] exampleFormula -- False
eval [False,True,False] exampleFormula -- True
sat :: BooleanFunction -> Bool
taut :: BooleanFunction -> Bool
returns true iff the Boolean function has at least one satisfying assignment. The function should be implemented using the above reduction rule.
returns true iff every assignment satisfies the Boolean function.