Christoph Schwarzweller: Haskell

Exercises (Haskell)

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

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

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

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.
Please define a function roots a b c, whose value are the roots of the quadratic polynomial ax^2 + bx + c.
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).
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 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]]
```
What are the (polymorphic) 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 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.
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 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.