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