Higher-Order Programming » Lab Sessions

Session 4 (Solutions)

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

Exercise 1: Iterative sum

(define (sum-iter lst) (define (sum-aux lst a) (if (null? lst) a (sum-aux (cdr lst) (+ (car lst) a)))) (sum-aux lst 0)) (define (product-iter lst) (define (product-aux lst a) (if (null? lst) a (product-aux (cdr lst) (* (car lst) a)))) (product-aux lst 1))

Exercise 2: Iterative Map / Filter

(define (deep-map lst f) (cond ((null? lst) lst) ((pair? lst) (cons (deep-map (car lst) f) (deep-map (cdr lst) f))) (else (f lst))))

The implementation of deep-map is straightforward. If the list is empty, the empty list will be returned. If the list is indeed a list (or its more generic form: a pair), then deep-map will be applied recursively on the car and cdr of the pair. Otherwise, we assume it to be a number, boolean, or other non-pair value, and we apply the supplied mapper function on it.

(define (deep-filter lst f) (cond ((null? lst) lst) ((pair? lst) (let* ((p1 (car lst)) (p2 (cdr lst)) (car-recursive (deep-filter p1 f)) (car-result (cond ((or (pair? p1) (null? car-recursive)) car-recursive) (else (car car-recursive)))) (cdr-result (deep-filter p2 f))) (cond ((and (null? car-result) (null? cdr-result)) '()) ((null? cdr-result) (list car-result)) ((null? car-result) cdr-result) (else (cons car-result cdr-result))))) (else (if (f lst) (list lst) '()))))

The implementation of deep-filter is more complicated. It follows the same pattern: check for empty list, check for pair, otherwise, execute the given function.

The third case is the most important one: since it can either return 1 or no values. This is implemented by it either returning a singleton list, or the empty list. However, we need to take into account the structure of the empty list. Therefore in the second case there are some additional checks on the type. If the recursive call on car is on a non-pair, this wrapped list needs to be removed via car.

Depending on whether both car and cdr have, or do not have, items to process, either only car or cdr can be returned, or a new pair.

The last peculiar case is when cdr-result is the empty list, then (list car-result) is returned. Since in this case the input element of deep-filter was a list (or at least a pair), the returned element should again be a list.

Exercise 3: Flatten

(define (flatten lst) (cond ((null? lst) '()) ((pair? lst) (append (flatten (car lst)) (flatten (cdr lst)))) (else (list lst)))) (flatten '(1 2 3 (4) 5 6 (((7 (8 9)))) 10 ((((((20)))))))) ; -> '(1 2 3 4 5 6 7 8 9 10 20)

By making use of append two lists are concatenated. Therefore, if the recursive calls on car and cdr return flattened lists, then they can easily be concatenated to create a larger flattened list. Therefore, in the last case of cond the elements are wrapped in a singleton list (a flattened list by definition) such that flatten can only receive flattened lists as arguments.

(define (accumulate-symbols lst) (let ((flat (flatten lst))) (filter flat symbol?))) (accumulate-symbols '(1 2 potato ((strawberry) 20 49) tomato)) ; -> (potato strawberry tomato)

The implementation of filter can be reused from previous exercises.

Section 2: Lambda and Let

Exercise 4: Convert to lambdas

let:

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

let*:

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

Exercise 5: A Lexical Bug

Conversion to lambda:

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

The variable x is a free variable that is not defined outside of lambda.

Fix:

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

By modifying the code such that let* is used instead of let.

Conversion to lambda (correct version):

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