Exercises (Haskell)

1. What are the values of the following expressions?
   

   > 10 
   
   > 5 + 3 + 4 
   
   > 9 - 1  
   
   > 6 / 2 
   
   > 2 * 3 + 4 * 6 
   
   > 7 < 9 
   
   > 3 <= 5 && 5 <= 3 
   
   > let a = 3 in a + 1 
   
   > let a = 1 in let b = a + 1 in a + b + a * b 
   
   > a 
   
   > let square n = n * n in square 4 
   
   > let fac n = if n == 0 then 1 else n * fac (n-1) in fac 5 
   

2. Please define functions gcd a b and lcm a b whose values are the greatest common divisor and the least common multiple of (natural numbers) a and b.
   
   
3. Please define functions smaller x y, greater x y, equal x y, smaller_equal x y, greater_equal x y, and not_equal x y.. No built-in functions are allowed except for < and boolean functions.
   
   
4. Please define a function same-values p1 p2 x y whose value is True, if p1(x,y) and p2(x,y) have the same value and False otherwise.

   Examples: > same-values == equal 3 1
             True
             > same-values < > 2 3
             False
             > same-values + * 2 2
             True
   

5. Please define functions odd n and even n checking whether a natural number n is odd or even, resp. No built-in functions are allowed except for True, False, ==, and a function "-1" calculating n-1 for natural numbers n.
   
   
6. Please define a function roots a b c, whose value are the roots of the quadratic polynomial ax^2 + bx + c.
   
   
7. The factorial n! 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).
   
   
8. 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).
   
   
9. 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.
   
   
10. 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 elements of l fulfilling the one-argument predicate p.
    
    c) Please define a function take_while p l that returns a list of elements of list l (starting from the left) until the first failure of predicate p. Examples:

      >take_while odd [1,3,5,6,7]
      [1,3,5]
      > take_while (\x -> x > 0) [1,4,2,-1,5]
      [1,4,2] 

    d) Please define a function groups l that will append consecutive identical elements from list l. Example:

      > compress [1,1,3,3,3,3,2,2,2,2,2,7,7,2,2]
      [[1,1],[3,3,3,3],[2,2,2,2,2],[7,7],[2,2]]

11. What are the (polymorphic) types of the functions defined in exercises 4,5,6,9 and 10?
    
    
12. 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 recursive 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.
    
    
13. Please define a function foldr analogous to function foldl. What is the type of foldr?
    
    
14. Using function foldl or foldr please define the following functions
    
    a) prod returning the product of the elements of list l
    
    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.
    
    
15. Please define the function insertionsort :: (a -> a -> Bool) -> [a] -> [a] using an appropriate higher order function.
    
    
16. 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 fⁿ.
    Examples:

    > iter square 2 3
      81
      > let f = iter square 2 in f 5
      625
      > iter square 0 7
      7 

17. Please define a function dc realizing the scheme for solving divide-and-conquer-problems. dc has the following (functional) arguments:
    
    
    1. test testing whether the problem instance is easy enough
    2. end solving easy enough problem instances
    3. divide dividing a problem into subproblems
    4. combine combining solutions of subproblems.
    
    Please define mergesort and Karatsuba-multiplication using dc.
    
    
18. Please complete the arithmetics of complex numbers as presented in the lecture
    
    a) using manifest types.
    
    b) using message passing.
    
    c) Please show how the expression

        angle (+c (make-rectangular -1 3) (make-polar 2 -2))

        is evaluated.
    
    
19. 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
    
    
20. 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'))
    
    
21. 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
    as well as {} |- 3 :: Int, {} |- 'a :: Char, {} |- [1,2,3] :: [Int], and {} |- ['a,'b,'c] :: [Char].
    
    
22. Please compute the most general type of the following functions.

    a) f []     = []
       f (x:xs) = (square x) : (f xs)
    
    b) append []     l = l
       append (x:xs) l = x : (append xs l)
    
    c) map f []     = []
       map f (x:xs) = (f x) : (map f xs)
    
    d) sum f []     = 0
       sum f (x:xs) = (f x) + (f xs)
    
    e) member x []     = False
       member x (y:ys) = (x == y) || (member x ys)
    

23. Suppose the following function sum is given.

    sum f x y = (f x) + (f y)
    

    Why does the expression sum length [1,2] ['a','b'] give a type error?
    Please define an alternative version of sum allowing summing up the lengths of [1,2] and ['a','b'].
    
    
24. 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].
    
    
25. Suppose the following type 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.
    
    
26. Please define a type Set a with functions member, subset, union, intersection, and delete.