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 2005generated with PLT Scheme