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.