Higher-Order Programming » Lab Sessions

Session 3 (Solutions)

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

Section 1: Pairs

Exercise 1.1:

(define (swap x) (cons (cdr x) (car x)))

Exercise 1.2:

(define (sort-pair x) (cons (min (car x) (cdr x)) (max (car x) (cdr x))))

Exercise 1.3:

(define (map-pair f g x) (cons (f (car x)) (g (cdr x))))

Exercise 1.4:

(define (fold-pair f x) (f (car x) (cdr x)))

Exercise 1.5:

(define (swap2 x) (fold-pair (lambda (y z) (cons z y)) x)) (define (sort-pair2 x) (fold-pair (lambda (y z) (if (<= y z) (cons y z) (cons z y))) x)) (define (map-pair2 f g z) (fold-pair (lambda (x y) (cons (f x) (g y))) z))

Section 3: Higher-Order Procedures on Lists

Exercise 3.1: Sum

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst))))) (define (accumulate proc default lst) (if (null? lst) default (proc (car lst) (accumulate proc default (cdr lst))))) (define (accumulate-iter proc default lst) (define (loop accum ptr) (if (null? ptr) accum (loop (proc accum (car ptr)) (cdr ptr)))) (loop default lst)) (define (sum-accum lst) (accumulate-iter + 0 lst))

sum can also be implemented using the higher-order procedure apply:

(define (sum lst) (apply + lst))

The + procedure takes an arbitrary amount of arguments. E.g. in order to calculate $a+b+c+d$, you can type (+ a b c d) instead of (+ a (+ b (+ c d))). apply applies the given procedure on a list of arguments.

Exercise 3.2: Filtering

(define (filter predicate lst) (cond ((null? lst) '()) ((predicate (car lst)) (cons (car lst) (filter predicate (cdr lst)))) (else (filter predicate (cdr lst))))) ; Without repetition of `(car lst)`, and `(filter predicate (cdr lst))` (define (filter2 predicate lst) (if ((null? lst) '()) (let* ((current (car lst)) (rest (cdr lst)) (result (predicate current)) (tail (filter predicate rest))) (if result (cons current tail) tail)))) (filter odd? '(4 8 15 16 23 42)) ; -> '(15 23) (define (my-predicate? x) (and (odd? x) (not (negative? x)))) (filter my-predicate? '(1 -1 2 -3 5 -8 13 -21 34 -55 89)) ; -> '(1 5 13 89)

Exercise 3.3: Reversing Lists

(define (reverse-aux acc lst) (if (null? lst) acc (reverse-aux (cons (car lst) acc) (cdr lst)))) (define (reverse lst) (reverse-aux '() lst))

Section 4: Higher-Order Procedures on Trees

Exercise 4.1: Sum and depth of a tree

(define (tree-sum tree) (cond ((null? tree) 0) ((not (pair? tree)) tree) (else (+ (tree-sum (car tree)) (tree-sum (cdr tree)))))) (display "tree-sum a: ") (display (tree-sum tree-a)) (newline) ; 6 (display "tree-sum b: ") (display (tree-sum tree-b)) (newline) ; 28 (display "tree-sum c: ") (display (tree-sum tree-c)) (newline) ; 10 (display "---") (newline) (define (tree-depth tree) (cond ((null? tree) 0) ((not (pair? tree)) 1) (else (+ (max (tree-depth (car tree)) (tree-depth (cdr tree))) 1)))) (display "tree-depth a: ") (display (tree-depth tree-a)) (newline) ; 3 (display "tree-depth b: ") (display (tree-depth tree-b)) (newline) ; 6 (display "tree-depth c: ") (display (tree-depth tree-c)) (newline) ; 3 (display "---") (newline) (define (tree-walk combiner neutral f tree) (cond ((null? tree) neutral) ((not (pair? tree)) (f tree)) (else (combiner (tree-walk combiner neutral f (car tree)) (tree-walk combiner neutral f (cdr tree)))))) (define (tree-sum2 tree) (tree-walk + 0 (lambda (x) x) tree)) (display "tree-sum2 a: ") (display (tree-sum2 tree-a)) (newline) ; 6 (display "tree-sum2 b: ") (display (tree-sum2 tree-b)) (newline) ; 28 (display "tree-sum2 c: ") (display (tree-sum2 tree-c)) (newline) ; 10 (display "---") (newline) (define (tree-depth2 tree) (tree-walk (lambda (left right) (+ (max left right) 1)) 0 (lambda (x) 1) tree)) (display "tree-depth2 a: ") (display (tree-depth2 tree-a)) (newline) ; 3 (display "tree-depth2 b: ") (display (tree-depth2 tree-b)) (newline) ; 6 (display "tree-depth2 c: ") (display (tree-depth2 tree-c)) (newline) ; 3 (display "---") (newline)

Exercise 4.2: Mapping the values on a tree.

During the exercise session, the solution to this exercise was given in error. This has been corrected.

(define (tree-map f tree) (cond ((null? tree) '()) ((not (pair? tree)) (f tree)) (else (cons (tree-map f (car tree)) (tree-map f (cdr tree)))))) (define (tree-map2 f tree) (tree-walk cons '() f tree))

Bonus Questions

Bonus Exercise 1: Cycle

(define (make-cycle a b c) (let ((lst (list a b c))) (set-cdr! (cddr lst) lst) lst)) (make-cycle 8 5 3)

This program displays #0=(8 5 3 . #0#).

Bonus Exercise 2: Generic Function Composition

(define (compose f g) (lambda args (g (apply f args))))