of a natural number n can be computed as follows.
fac n = fac_help n 1
where fac_help 0 acc = acc
fac_help n acc = silnia_help (n - 1) (n * acc)
Here the variable acc of function fac_help is called an accumulator.
Please define a function
fib n, whose value is the n-th element of the Fibonacci sequence
(give two versions of fib: one recursive and one using accumulators).
The exponentiation b^e (for natural numbers b and e)
can be computed using b^e = (b^(e/2))^2.
Please write an exponentiation function exp b e using this property
(again one version using recursion and one using accumulators).
Please define the following functions for lists:
a) append l m concatenating l i m.
b) member x l checking whether x is an element of l
c) reverse l reversing l.
d) last l giving the last element of l.
e) delete x l erasing x from l.
f) pairing l1 l2, transforming
l1 i l2 into a list of corresponding pairs. Example:
> pairing [1,2,3] [a,b,c]
[(1,a),(2,b),(3,c)]
g) split x l splitting l into two lists l1 i l2, where
l1 contains the elements smaller than
x and l2 the elements greater than x.
h) map f l applying the one-argument function f
to all elements of l.
a) Please define a function map2 f l1 l2 applying the one-argument function f
to all elements of l1 i l2. Example:
> map2 (+) [1,2,3] [8,9,10]
[9,11,13]
b) Please define a function filter p l, whose value is the list of all element of l
fulfilling the one-argument predicate p.
What are the types of the functions defined in exercises 4,5,6,9 and 10?
a) Please define a function product term next a b analogous to function sum.
Please show, how product can be used to define both function
factorial and the approximation of p using the formula
p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3
· 3 · 5 · 5 · 7 · 7 ··· .
b) Please define a function accumulate combiner null-value term a next b generalizing functions sum i product:
The arguments term, next, a, and b are the same as in the definitions of
sum i prod.
combiner is a two-argument function describing, how term a is tied together
with the recursive result.
null-value is the initial value used in the basic step of recursion.
Please also show, how sum i product can be defined using
accumulate.
c) Even accumulate can be generalized:
Please define a function filter-accumulate with an additional argument pred.
pred is a one-argument predicate and filter-accumulate ties term a to the result only if
a fulfills pred.
Using filter-accumulate please compute the sum of squares of the prime numbers
in the interval [a,b]
and the product of the natural numbers i smaller than n for which gcd(i,n) = 1.
Please define a function foldr analogous to function foldl.
What is the type of foldr?
Using function foldl or foldr please define the following functions
a) prod
b) length
c) and (for a list of Boolean values)
d) gcd (for a list of natural numbers)
e) reverse
f) delete
g) map
h) filter pred
i) forall pred.
Please define the function insertionsort :: (a -> a -> Bool) -> [a] -> [a]
using an appropriate higher order function.
Please define a function iter f n for a one-argument function f and a natural number n.
The value of iter f n is a function computing fn.
Examples: > iter square 2 3
81
> let f = iter square 2 in f 5
625
> iter square 0 7
7
Please define a function dc realizing the scheme for solving divide-and-conquer-problems.
dc has the following (functional) arguments:
- test testing whether the problem instance is easy enough
- end solving easy enough problem instances
- divide dividing a problem into subproblems
- combine combining solutions of subproblems.
Please define mergesort and Karatsuba-multiplication using dc.
What are the types of the following expressions?
a) +
b) + 37
c) append
d) append [1,2]
e) map
f) map square [1,2,3,4,5]
g) map square [['a']]
h) map length [['a']]
i) foldl
j) foldl (++)
k) foldl (++) []
l) f 7
m) \f -> f 7
n) + (f x) (g x)
o) f 7 (g 'x')
p) \f -> f (g x)
q) (\f -> f (g x)) square
Please compute the most general unifier -- if it exists -- of
a) f(x,g(b)) f(a,y)
b) f(h(x,b),y) f(h(a,y),x)
c) f(x,y) f(h(x,b),y)
d) g(x,h(x,y),h(y,h(x,y))) g(x,y',h(z,y'))
e) g(x,h(x,y),h(y,h(x,y))) g(x,y',h(y',z))
f) f(a,x,h(g(y))) f(z,h(z),h(z'))
Please compute the most general type of the following expressions.
a) map square [1,2,3]
b) map square ['a','b','c']
c) \x -> 2 * x
d) \f -> f 3
e) \f x -> f (f x)
f) (\f x -> f (f x)) square
g) \x -> x x
h) f 7 (g 'a')
You can use {} |- map :: (a -> b) -> [a] -> [b] and {} |- square :: Int -> Int.
Please compute the most general type of the following functions.
a) map f [] = []
map f (x:xs) = (f x) : (map f xs)
b) append [] l = l
append (x:xs) l = x : (append xs l)
c) sum f [] = 0
sum f (x:xs) = (f x) + (f xs)
d) member x [] = False
member x (y:ys) = (x == y) || (member x ys)
Suppose the folowing function sum/tt is given.
sum f l1 l2 = (f l1) + (f l2)
Why does the expression sum length [1,2] ['a','b'] give an error?
Please given an alternative version of sum allowing summing up the lengths
of [1,2] and ['a','b'].
a) Please define a function position x l finding the position of x in list l.
Use the type Maybe a to define position.
b) Please define a function drop n l eliminating the first n elements of list l.
Use the type Maybe a to define drop.
c) Please define a function sum l summing up the elements of a list with type [Maybe a].
Suppose the following typ of binary trees is given.
data BinTree a = Leaf a | Node a (BinTree a) (BinTree a)
Please define the following functions.
a) heightBinTree t computing the height of tree t.
b) sizeBinTree t computing the number of nodes in tree t.
c) maxBinTree t computing the biggest element of tree t.
d) postBinTree t whose value is the list of t's elements in postorder.
What are the types of the functions?
Please also realize functions a) - d) using a - yet to define - function foldBinTree.
Suppose the following typ of trees is given.
data Tree a = Node a [Tree a]
Please define the following functions.
a) sizeTree t computing the number of nodes in tree t.
b) sumTree t summing up all elements of tree t.
c) preTree t whose value is the list of t's elements in preorder.
Please also realize functions a) - c) using a - yet to define - function foldTree.
Please define a type Set a with functions member,
subset, union, intersection, and delete.
Please define trees with sets attached to its nodes and functions
a) deleteTree x t eliminating a given element x from all of t's lists.
b) unionTree t giving a list of all elements in t.
c) allTree x t checking whether element x appears in all of t's.
Suppose the following type of Boolean expressions is given.
data BoolExpr = Value Bool
| And BoolExpr BoolExpr
| Not BoolExpr
a) What is the representation of (¬ False ∧ True) ∧ True ?
b) Please define a function eval :: BoolExpr -> Bool evaluating Boolean expressions.
c) Please define a function foldBoolExpr for compressing Boolean expressions.
What is the type of foldBoolExpr?
d) Please define function eval using foldBoolExpr.
Please define types BinTree a and Set a
as instances of type classes Show, Eq, and Ord.
a) Please define a type class Stack s.
b) Please define an instance of Stack s using constructors.
c) Please define an instance of Stack s by wrapping lists.
There have already been defined functions map i fold for lists and other types.
Please overload these functions using type classes.
Please also define functions map and fold for sets defined in exercise 27.