Higher-Order Programming » Lab Sessions

Session 4

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

Section 1: Recursion and Iteration (Again)

Exercise 1: Iterative sum

In the previous exercise session you have implemented procedures that calculate the total sum of a list. The solution is shown below.

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

Rewrite this procedure using iteration, instead of recursion. Do the same for product.

Hint! Iteration in Scheme can be reached by making use of tail-call recursion optimisation.

Exercise 2: Deep Map / Filter

Create two procedures that filter, map values in a nested list structure.

(define a '(1 2 3 (4 5) 6)) (deep-map add1 a) ; -> '(2 3 4 (5 6) 7)) (deep-filter odd? a) ; -> '(1 3 (5))

Hint! For deep-filter you need more than 3 branches for all the possible combinations in which filtered car and filtered cdr values of pairs can exist.

Exercise 3: Flatten

1. Write a procedure flatten that flattens nested lists into a single list.
2. Write a procedure accumulate-symbols that uses flatten but removes all non-symbolic values from a nested list structure.

Section 2: Lambda and Let

Exercise 4: Convert to lambdas

Convert the following two programs to equivalent syntax using lambda.

(let ((a 5) (b (+ 2 10))) (+ a b))

(let* ((a 5) (b (+ 2 a))) (* a b))

Exercise 5: A Lexical Bug

The following program contains a bug.

(let ((x 10) (y (fac x)) (z (/ y x))) (+ x y z))

Explain why this program fails using by converting the program text using lambda. Fix the bug, and convert it again to only lambdas.