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 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 element of l fulfilling the one-argument predicate p.

  11. What are the 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 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

    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 fn.
    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. 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

  19. 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'))

  20. 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.

  21. 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)
    
  22. 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'].

  23. 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].

  24. 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.

  25. 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.

  26. Please define a type Set a with functions member, subset, union, intersection, and delete.

  27. 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.

  28. 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.

  29. Please define types BinTree a and Set a as instances of type classes Show, Eq, and Ord.

  30. 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.

  31. 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.