Higher-Order Programming » Lab Sessions

Session 5 (Solutions)

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

Section 1: More higher-order functions on lists

(define (accumulate proc default lst) (if (null? lst) default (proc (car lst) (accumulate proc default (cdr lst)))))

Exercise 1:

(define (product lst) (accumulate * 1 lst)) (define (minimum lst) (accumulate min +inf.0 lst)) (define (maximum lst) (accumulate max -inf.0 lst)) (define (append2 lst1 lst2) (accumulate cons lst2 lst1)) (define (concat lst) (accumulate append '() lst)) (define (filter p lst) (accumulate (lambda (x xs) (if (p x) (cons x xs) xs)) '() lst)) (define (eval-polynomial p x) (accumulate (lambda (c r) (+ c (* x r))) 0 p)) (define (flatmap proc lst) (accumulate (lambda (x xs) (append (proc x) xs)) '() lst))

Exercise 2:

1. (define (filter2 p lst) (flatmap (lambda (x) (if (p x) (list x) '())) lst))

2. ; Helper function to create a list of numbers from m through n. (define (from-to m n) (if (<= m n) (cons m (from-to (+ m 1) n)) '())) ; 'Non-deterministic' iteration over a range (define (for-range m n f) (flatmap f (from-to m n))) ; Predicate to test for a triple. (define (pythagorean-triple? a b c) (= (+ (* a a) (* b b)) (* c c))) (define (pythagorean-triples n) (for-range 1 n (lambda (a) (for-range a n (lambda (b) (for-range b n (lambda (c) (if (pythagorean-triple? a b c) ; Success: return a result as a singleton list (list (list a b c)) ; Fail: return an empty list '()))))))))

Section 2: Streams

Exercise 3: Streams Primer

(define (take-n n str) (if (or (<= n 0) (empty-stream? str)) '() (cons (head str) (take-n (- n 1) (tail str))))) (define (create-ints-from n) (cons-stream n (create-ints-from (+ n 1)))) (define (create-pos-ints) (create-ints-from 1)) (define pos-ints (create-pos-ints)) (define (create-odd-pos-ints) (define (aux n) (cons-stream n (aux (+ n 2)))) (aux 1)) (define (divisible n p) (= 0 (remainder n p))) (define odd-pos-ints-expl (create-odd-pos-ints)) (define odd-pos-ints-filt (streamfilter odd? pos-ints)) (define pos-ints-coprime-235 (streamfilter (lambda (x) (not (or (divisible x 2) (divisible x 3) (divisible x 5)))) pos-ints))

Exercise 4: Stream transformers

1. Pairwise combination

(define (stream-zip-with f xs ys) (if (or (empty-stream? xs) (empty-stream? ys)) the-empty-stream (cons-stream (f (head xs) (head ys)) (stream-zip-with f (tail xs) (tail ys))))) (define (stream-pairwise-sum xs ys) (stream-zip-with + xs ys)) (define (stream-pairwise-product xs ys) (stream-zip-with * xs ys))

2. Prefix calculation

   (define (stream-prefix comb def str) (cons-stream def (if (empty-stream? str) the-empty-stream (stream-prefix comb (comb def (head str)) (tail str))))) (define (stream-prefix-sum xs) (stream-prefix + 0 xs)) (define (stream-prefix-product xs) (stream-prefix * 1 xs))

3. Stream interleaving

   (define (stream-interleave xs ys) (if (empty-stream? xs) the-empty-stream (cons-stream (head xs) (stream-interleave ys (tail xs)))))

Exercise 5: Numerical Approximation

(define (fact n) (if (< n 2) 1 (* n (fact (- n 1))))) (define (alternate-sign) (stream-interleave (stream-const 1.0) (stream-const -1.0))) (define (sin-summands x) (stream-zipwith (lambda (n s) (/ (* s (expt x n)) (fact n))) (create-odd-pos-ints) (alternate-sign))) (define (stream-ref str pos) (if (<= pos 0) (head str) (stream-ref (tail str) (- pos 1)))) (define (sin-approx x n) (stream-ref (stream-prefix-sum (sin-summands x)) n))

(define (pi-factor n) (let ((nom (* (- n 1) (+ n 1.0))) (den (* n n))) (/ nom den))) (define (pi-factors) (map-stream pi-factor (tail (create-odd-pos-ints)))) (define (pi-approx n) (* 4.0 (stream-ref (stream-prefix-product (pi-factors)) n)))

Exercise 6: Collatz Streams

Finite (?) Collatz:

(define (collatz-stream n) (cons-stream n (if (= n 1) the-empty-stream (collatz-stream (if (even? n) (/ n 2) (+ (* n 3) 1)))))) (print-stream (collatz-stream 11)) ; -> [11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 ]

Infinite Collatz:

(define (inf-collatz-stream n) (cons-stream n (inf-collatz-stream (if (even? n) (/ n 2) (+ (* n 3) 1))))) (print-stream (inf-collatz-stream 11)) ; -> [11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4 2 1 4 2 1 4 2 1 ...

Numbers keep being printed on the stream, but as the stream is only generated while print-stream is recursively reading the next element of a stream, no out of memory error will be generated. However, the Read-Eval-Print Loop will be stuck. You can so stop the execution of the program using CTRL + K (⌘ + K on Mac).

Exercise 7: Streams Advanced

(define integers (cons-stream 1 (stream-pairwise-sum ones integers)))

(define fibs (cons-stream 0 (cons-stream 1 (stream-pairwise-sum (tail fibs) fibs)))) (print-stream 10 fibs) ; -> '(0 1 1 2 3 5 8 13 21 34)

(define facs (cons-stream 1 (stream-pairwise-product facs integers))) (take-n 10 facs) ; -> (1 1 2 6 24 120 720 5040 40320 362880)