Teaching 211 F '05 Assignments Set 1 Set 2 Set 3 Set 4 Set 5 Set 6 Set 7 Set 8 Set 9 Set 10 Set 11 Set 12 Set 13 Set 14

### Problem Set 9

If you run any of the functions (as opposed to just testing them), comment out the code for running the functions before you submit your solution.

N.B.: Tests are not runs. A test is when you evaluate an expression and compare it to some expected result, while a run is when you evaluate an expression without anticipating any particular result for the expression.

Due date: 11/10 @ NOON

This problem set covers abstraction and "loops" again.

HtDP Problems:

21.2.1, 21.2.2(2), 21.2.3(2)

Problem 1:

Parameteric S-expressions are like those you know as Web pages but they may contain all kinds of things:

``````
;; An [S-exp X] is one of:
;; -- empty
;; -- (cons [S-exp X] [S-exp X])
;; -- (cons X [S-exp X])
```
```
Make up one example per [S-exp Number], [S-exp Symbol], and [S-exp (union Number Symbol)].

Here are two functions that traverse S-expressions and process the leafs (X):
 `````` ;; count : X [S-exp X] -> Number ;; count all occurrences ;; of x in s (define (count x s) (cond [(empty? s) 0] [(cons? (first s)) (+ (count x (first s)) (count x (rest s)))] [else (cond [(equal? (first s) x) (+ (count x (rest s)) 1)] [else (count x (rest s))])])) `````` `````` ;; rpl : Y X [S-exp X] -> [S-exp Y] ;; replace all occurrences ;; of old in s with new (define (rpl new old s) (cond [(empty? s) empty] [(cons? (first s)) (cons (rpl new old (first s)) (rpl new old (rest s)))] [else (cond [(equal? (first s) old) (cons new (rpl new old (rest s)))] [else (cons (first s) (rpl new old (rest s)))])])) ``````

Design the common abstraction traverse and a general contract.

Design the function

``````
;; sum : [S-exp Number] -> Number
;; compute the sum of all numbers
;; that occur in the given S-expression
```
```
For full credit, define the final version in terms of traverse. Remember that design is not a one-stop activity.

Design the function

``````
;; rem : Symbol [S-exp Symbol] -> [S-exp Symbol]
;; remove all occurrences of x from s
(define (rem x s) ...)
```
```
For full credit, define the final version in terms of traverse.

Design the function

``````
;; flatten : [S-exp X] -> [Listof X]
;; collect all X's in a list
```
```
For full credit, define the final version in terms of traverse.

Determine which of these three functions are parameteric and which are not. Explain why.

Problem 2:

Define the following function using a loop:

``````
;; number-of : List-of-digits -> Number
;; convert a list of digits [0..9] into a number
;; the least-significant digit is first
(define (number-of lod)
(cond
[(empty? lod) 0]
[else (+ (first lod) (* 10 (number-of (rest lod))))]))

;; Tests:
(= (number-of (list 9)) 9)
(= (number-of (list 1 9)) 91)
```
```

Define the following function using a loop:

``````
;; juxtapose : Image Image -> Image
;; create a single image by aligning
;; the right side of i with the left of j
(define (juxtapose i j)
(overlay/xy i (image-width i) 0 j))

;; juxtapose : (cons Image (Listof Image)) -> Image
;; juxtapose a non-empty list of images
(define (juxtapose* loi)
(cond
[(empty? (rest loi)) (first loi)]
[else (juxtapose (first loi)
(juxtapose* (rest loi)))]))

;; Tests:
(define image1 (rectangle 10 10 'solid 'green))
(define image2 (rectangle 10 10 'solid 'blue))
(define image3 (rectangle 10 10 'solid 'red))

(define image1+2
(overlay/xy (rectangle 20 10 'solid 'green)
5 0
(rectangle 10 10 'solid 'blue)))
(define image123
(overlay/xy image1+2 15 0 (rectangle 10 10 'solid 'red)))

(equal? (juxtapose image1 image2)
image1+2)
(equal? (juxtapose* (list image1 image2 image3))
image123)
```
```
Hint: Experiment and see for yourself. Then guess.

Define bulls-eye using loops:

``````
;; bulls-eye : NaturalNumber -> Image
;; draw a black bull's eye with i rings with distance 10
(define (bulls-eye i)
(draw (indices i 10)))

;; indices : NaturalNumber Number -> (Listof Number)
;; create i * delta, ..., delta
(define (indices i delta)
(cond
[(zero? i) empty]
[else (cons (* i delta) (indices (sub1 i) delta))]))

;; draw : (cons Number (Listof Number)) -> Image
;; create bull's eye from concentric radii
(define (draw l)
(cond
[(empty? (rest l)) (circle (first l) 'outline 'black)]
[else (overlay (circle (first l) 'outline 'black)
(draw (rest l)))]))
```
```
Start by developing exercises and turning them into tests. Hint: Here is a small experiment:
``````
> (indices 3 10)
(list 30 20 10)
> (build-list 3 (lambda (i) (* 10 (+ i 1))))
(list 10 20 30)
```
```
Use the insight. You may wish to proceed in a step-wise fashion and reorganize the program as you go.

 last updated on Sat Nov 26 15:34:41 EST 2005 generated with PLT Scheme