Higher-Order Programming » Lab Sessions

Session 2

Assistant: Steven Keuchel (steven.keuchel@vub.be)

Section 1: More Higher-Order Procedures

Exercise 1: Implement the function flip which takes a two-parameter function and produces a new two-parameter function with the order of the parameters flipped.

((flip -) 1 2) ; -> 1 ((flip string-append) "abc" "def") ; -> "defabc"

Exercise 2: Implement the function iterate that takes three parameters f, n and x that applies f to x n-times, i.e. (iterate f 3 x) calculates (f (f (f x))).

(define (louder s) (string-append s "!")) (iterate louder 3 "Hi") ; -> "Hi!!!"

Similarly, implement a function iterate-until that takes three parameters f, p and x that iterates f on x until the predicate p holds on the iteration value.

(define (collatz-step n) (display n) (display " ") (if (even? n) (/ n 2) (+ (* n 3) 1))) (iterate-until collatz-step (lambda (x) (= x 1)) 3) ; -> 3 10 5 16 8 4 2 1 (iterate-until louder (lambda (s) (>= (string-length s) 15)) "Hello World") ; -> "Hello World!!!!"

Exercise 3: Implement the function pointwise-avg which takes two parameters:

• a one-parameter function f and
• a one-parameter function g.

pointwise-avg should create a new one-parameter function that calculates the pointwise average of f and g. Test your function using the following example:

(define f (lambda (x) x)) (define g (lambda (x) (* 2 x))) (define fg (pointwise-avg f g)) (fg 2) ; -> 3 (fg 4) ; -> 6

Similarly, define functions pointwise-min and pointwise-max.

Exercise 4: The functions from Exercise 3 have a similar structure and this repetition can be avoided by carefully abstracting over the parts that are specific to one function. Define a new generic function pointwise that can be instantiated to each of the specific ones from exercise 3, e.g. (pointwise min) should behave like pointwise-min.

Bonus Exercises: Church Booleans

Two-parameter functions of Scheme can serve as an implementation model for Boolean arithmetic. In this model, booleans are encoded as making a choice between the two parameters. true chooses the first parameter and false chooses the second, i.e.

(define true (lambda (x y) x)) (define false (lambda (x y) y))

Using the above, the Scheme`s booleans can be straightforwardly embedded in the encoding.

(define (choose b) (if b true false))

Logical connectives can also be implemented in this model, for instance conjunction:

(define (and p q) (p q p)) ((and true true) 1 2) ; -> 1 ((and true false) 1 2) ; -> 2 ((and false true) 1 2) ; -> 2 ((and false false) 1 2) ; -> 2

Bonus Exercise B1: Define choose directly without referring to true and `false**.

Bonus Exercise B2: Implement the logical connectives not, or and xor. Hint: Reuse not in the definition of xor.