Exercises (Scheme)

1. What are the values of the following expressions?
   
   

   > 10 
   
   > (+ 5 3 4) 
   
   > (- 9 1) 
   
   > (/ 6 2) 
   
   > (+ ( * 2 4) (- 4 6)) 
   
   > (let ((a 1) (b 2)) (+ a b (* a b))) 
   
   > a 
   
   > (define a 3) 
   
   > a
   
   > (define b (+ a 1)) 
   
   > (+ a b (* a b)) 
   
   > (= a b) 
   
   > (if (and (> b a) (< b (* a b))) 
         b 
         a) 
   
   > (cond ((= a 4) 6) 
           ((= b 4) (+ 6 7 a))
           (else    25))
   

2. Please define functions (new.< x y), (new.> x y), (new.= x y), (new.<= x y), (new.>= x y), and (new.<> x y). No built-in functions are allowed, except for < and boolean functions.
   
   
3. 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.
   
   
4. Please define a function (same-values? p1 p2 x y) whose value is #t, if p1(x,y) i p2(x,y) have the same value and #f otherwise.

   Examples: > (same-values? = new.= 3 1)
             #t
             > (same-values? < > 2 3)
             #f
             > (same-values? + * 2 2)
             #t
   

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 #t, #f, zero? and a function "-1" calculating n-1.
   
   
6. a) Please define a function (factorial n) whose value is n! using recursion.
   
   b) The factorial function can also be defined the following way:

     (define (factorial_help n i acc)
         (if (< n i)
             acc
             (factorial_help n (+ i 1) (* i acc))))
   
      (define (factorial n)
         (factorial_help n 1 1))
   

   Please show how the expression (factorial 4) is evaluated, once for version a) and again for version b).
   Note: The argument acc is called accumulator and one says that this version defines the faculty function using accumulation (or iteratively).
   
   
7. a) Please define functions (fibonacci n) whose value is the n-th element of the Fibonacci sequence, one using recursion and one using accumulation.
   
   b) For both versions please show how the expression (fibonacci 4) is evaluated.
   
   
8. a) The exponentiation b^e (for natural numbers b and e) can be faster executed using b^e = (b^(e/2))^2.
       Using this property please define functions (exp b e) whose value is b^e, one recursive function and one using accumulation.
   
   b) For both versions please show how the expression (exp 2 6) is evaluated.
   
   
9. Please define a function (root f a b) approximating a root of f between a and b using the half-interval-method.
   
   
10. Why the expression if cannot be defined the following way?

    (define (new-if condition consequence alternative)
       (cond (condition consequence)
             (else      alternative)))
    

11. Please define a function (product term next a b) analogous to function sum.
    Please show, how function product can be used to define both function factorial and for the approximation of p using the formula   p/4 = 2 · 4 · 4 · 6 · 6 · 8 ··· / 3 · 3 · 5 · 5 · 7 · 7 ··· .
    
    
12. 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.
    
    
13. Even function 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.
    
    
14. Suppose the following definition of function f is given.

    (define f g) (g 2))
    

    Please show how the following expressions are evaluated.
    
    a) (f square)
    
    b) (f (lambda (z) (+ z (* 3 z)))
    
    c) (f f)
    
    
15. Suppose the following function definitions com, square, and double are given.

    (define (comb f g)
       (lambda (x) (f (g x))))
    
    (define (square n) (* n n))
    
    (define (double n) (+ n n))
    

    Please show how the expression ((comb square double) 5) is evaluated.
    
    
16. Please define a function (iter f n), whose value is the function fⁿ, where f⁰ = id and fⁿ⁺¹ = f ∘ fⁿ.