33 Solutions

This appendix contains solutions to selected exercises.

33.1 Solution: Complex, with class

This is a solution for the Complex, with class exercise.

#lang class/0

; ==========================================================

; Complex Structure

; A Complex is a (make-complex Real Real).

; Interp: real and imaginary parts.

(define-struct complex (real imag))

; =? : Complex Complex -> Boolean

; Are the complexes equal?

(check-expect (=? (make-complex 0 0) (make-complex 0 0)) true)

(check-expect (=? (make-complex 0 0) (make-complex 2 3)) false)

(define (=? n m)

(and (= (complex-real n)

(complex-real m))

(= (complex-imag n)

(complex-imag m))))

; plus : Complex Complex -> Complex

; Add the complexes.

(check-expect (plus (make-complex 2 3) (make-complex 4 5))

(make-complex 6 8))

(define (plus n m)

(make-complex (+ (complex-real n) (complex-real m))

(+ (complex-imag n) (complex-imag m))))

; minus : Complex Complex -> Complex

; Subtract the complexes.

(check-expect (minus (make-complex 2 3) (make-complex 4 5))

(make-complex -2 -2))

(define (minus n m)

(make-complex (- (complex-real n) (complex-real m))

(- (complex-imag n) (complex-imag m))))

; times : Complex Complex -> Complex

; Multiply the complexes.

(check-expect (times (make-complex 2 3) (make-complex 4 5))

(make-complex -7 22))

(define (times n m)

(make-complex (- (* (complex-real n) (complex-real m))

(* (complex-imag n) (complex-imag m)))

(+ (* (complex-imag n) (complex-real m))

(* (complex-real n) (complex-imag m)))))

; div : Complex Complex -> Complex

; Divide the complexes.

(check-expect (div (make-complex 2 3) (make-complex 4 5))

(make-complex 23/41 2/41))

(define (div n m)

(make-complex (/ (+ (* (complex-real n) (complex-real m))

(* (complex-imag n) (complex-imag m)))

(+ (sqr (complex-real m))

(sqr (complex-imag m))))

(/ (- (* (complex-imag n) (complex-real m))

(* (complex-real n) (complex-imag m)))

(+ (sqr (complex-real m))

(sqr (complex-imag m))))))

; sq : Complex -> Complex

; Multiply the complex by itself.

(check-expect (sq (make-complex 0 1))

(make-complex -1 0))

(define (sq n)

(times n n))

; mag : Complex -> Number

; Compute the magnitude of the complex.

(check-expect (mag (make-complex -1 0)) 1)

(check-expect (mag (make-complex 3 4)) 5)

(define (mag n)

(sqrt (+ (sqr (complex-real n))

(sqr (complex-imag n)))))

; sqroot : Complex -> Complex

; Compute the square root of the complex.

(check-expect (sqroot (make-complex -1 0))

(make-complex 0 1))

(define (sqroot n)

(make-complex (sqrt (/ (+ (mag n) (complex-real n)) 2))

(* (sqrt (/ (- (mag n) (complex-real n)) 2))

(if (negative? (complex-imag n))

-1

1))))

; to-number : Complex -> Number

; Convert the complex to a Racket complex number.

(check-expect (to-number (make-complex 2 3)) 2+3i)

(define (to-number n)

(+ (complex-real n)

(* 0+1i (complex-imag n))))

; Alternative:

; OK, this relies on knowing about ‘make-rectangular'.

; (define (to-number n)

;   (make-rectangular (complex-real n)

;                     (complex-imag n)))

; ==========================================================

; Complex Class

; A Complex is a (new complex% Real Real).

; Interp: real and imaginary parts.

(define-class complex%

(fields real imag)

; =? : Complex -> Boolean

; Is the given complex equal to this one?

(check-expect (send (new complex% 0 0) =? (new complex% 0 0)) true)

(check-expect (send (new complex% 0 0) =? (new complex% 2 3)) false)

(define (=? n)

(and (= (send this real)

(send n real))

(= (send this imag)

(send n imag))))

; plus : Complex -> Complex

; Add the given complex to this one.

(check-expect (send (new complex% 2 3) plus (new complex% 4 5))

(new complex% 6 8))

(define (plus n)

(new complex%

(+ (send this real) (send n real))

(+ (send this imag) (send n imag))))

; minus : Complex -> Complex

; Subtract the given complex from this one.

(check-expect (send (new complex% 2 3) minus (new complex% 4 5))

(new complex% -2 -2))

(define (minus n)

(new complex%

(- (send this real) (send n real))

(- (send this imag) (send n imag))))

; times : Complex -> Complex

; Multiply the given complex by this one.

(check-expect (send (new complex% 2 3) times (new complex% 4 5))

(new complex% -7 22))

(define (times n)

(new complex%

(- (* (send this real) (send n real))

(* (send this imag) (send n imag)))

(+ (* (send this imag) (send n real))

(* (send this real) (send n imag)))))

; div : Complex -> Complex

; Divide this complex by the given one.

(check-expect (send (new complex% 2 3) div (new complex% 4 5))

(new complex% 23/41 2/41))

(define (div n)

(new complex%

(/ (+ (* (send this real) (send n real))

(* (send this imag) (send n imag)))

(+ (sqr (send n real))

(sqr (send n imag))))

(/ (- (* (send this imag) (send n real))

(* (send this real) (send n imag)))

(+ (sqr (send n real))

(sqr (send n imag))))))

; sq : -> Complex

; Multiply this complex by itself.

(check-expect (send (new complex% 0 1) sq)

(new complex% -1 0))

(define (sq)

(send this times this))

; Alternative:

; OK, but ‘this' solution is preferred.

; (define (sq)

;   (times (new complex%

;               (send this real)

;               (send this imag))))

; Alternative:

; Not OK: no code re-use.

; (define (times n)

;   (new complex%

;        (- (* (send this real) (send this real))

;           (* (send this imag) (send this imag)))

;        (+ (* (send this imag) (send this real))

;           (* (send this real) (send this imag)))))

; mag : -> Number

; Compute the magnitude of this complex.

(check-expect (send (new complex% -1 0) mag) 1)

(check-expect (send (new complex% 3 4) mag) 5)

(define (mag)

(sqrt (+ (sqr (send this real))

(sqr (send this imag)))))

; sqroot : -> Complex

; Compute the square root of this complex.

(check-expect (send (new complex% -1 0) sqroot)

(new complex% 0 1))

(define (sqroot)

(new complex%

(sqrt (/ (+ (send this mag) (send this real)) 2))

(* (sqrt (/ (- (send this mag) (send this real)) 2))

(if (negative? (send this imag))

-1

1))))

; to-number : -> Number

; Convert this complex to a Racket complex number.

(check-expect (send (new complex% 2 3) to-number) 2+3i)

(define (to-number)

(+ (send this real)

(* 0+1i (send this imag)))))

33.2 Solution: Lists of Numbers

This is a solution for the Lists of Numbers exercise.

#lang class/0

;; ==========================================================

;; Lists of Numbers

;; INTERFACE

;; ---------

;; A ListofNumber implements:

;;

;; - length : -> Natural

;;   Count the number of elements in this list.

;;

;; - append : ListofNumber -> ListofNumber

;;   Append the elements of this list with the given list.

;;

;; - sum : -> Number

;;   Add all the elements of this list.

;;

;; - prod : -> Number

;;   Multiply all the elements of this list.

;;

;; - contains? : Number -> Boolean

;;   Is the given number an element in this list?

;;

;; - reverse : -> ListofNumber

;;   Reverse the elements of this list.

;;

;; - map : [Number -> Number] -> ListofNumber

;;   Apply given function to each element of this list and

;;   construct a list of the results

;;

;; - max-acc : Number -> Number

;;   Find largest number between given and this list of numbers.

;;

;; A NeListofNumber implements ListofNumber and:

;;

;; - max : -> Number

;;   Find largest number in this non-empty list.

;; IMPLEMENTATION

;; --------------

;; A (new empty%) implements ListofNumber

;; A (new cons% Number ListofNumber) implements NeListofNumber

(define-class empty%

(check-expect (send mt length) 0)

(define (length) 0)

(check-expect (send mt append ls) ls)

(define (append ls) ls)

(check-expect (send mt sum) 0)

(define (sum) 0)

(check-expect (send mt prod) 1)

(define (prod) 1)

(check-expect (send mt contains? 5) false)

(define (contains? n) false)

(check-expect (send mt reverse) mt)

(define (reverse) this)

(check-expect (send mt reverse-acc ls) ls)

(define (reverse-acc ls) ls)

(check-expect (send mt map add1) mt)

(define (map f) this)

(check-expect (send mt max-acc 5) 5)

(define (max-acc a) a))

(define-class cons%

(fields first rest)

(check-expect (send ls length) 3)

(define (length)

(add1 (send (send this rest) length)))

(check-expect (send ls append mt) ls)

(define (append ls)

(new cons%

(send this first)

(send (send this rest) append ls)))

(check-expect (send ls sum) 9)

(define (sum)

(+ (send this first)

(send (send this rest) sum)))

(check-expect (send ls prod) 24)

(define (prod)

(* (send this first)

(send (send this rest) prod)))

(check-expect (send ls contains? 5) false)

(check-expect (send ls contains? 2) true)

(define (contains? n)

(or (= n (send this first))

(send (send this rest) contains? n)))

(check-expect (send ls reverse)

(new cons% 4 (new cons% 2 (new cons% 3 mt))))

(define (reverse)

(reverse-acc (new empty%)))

(check-expect (send ls reverse-acc ls)

(new cons% 4 (new cons% 2 (new cons% 3 ls))))

;; ACCUM: elements seen in reverse order.

(define (reverse-acc ls)

(send (send this rest) reverse-acc

(new cons% (send this first) ls)))

(check-expect (send ls map add1)

(new cons% 4 (new cons% 3 (new cons% 5 mt))))

(define (map f)

(new cons% (f (send this first))

(send (send this rest) map f)))

(check-expect (send ls max-acc 8) 8)

(check-expect (send ls max-acc 0) 4)

;; ACCUM: largest number seen so far.

(define (max-acc a)

(send (send this rest) max-acc

(cond [(> (send this first) a)

(send this first)]

[else a])))

(check-expect (send ls max) 4)

(define (max)

(send (send this rest) max-acc (send this first))))

(define mt (new empty%))

(define ls (new cons% 3 (new cons% 2 (new cons% 4 mt))))

33.3 Solution: Home on the Range

This is a solution for the Home on the Range exercise.

#lang class/0

; A Range is one of

; - (new range% Number Number)

; Interp: represents the range between ‘lo' and ‘hi'

;         including ‘lo', but *not* including ‘hi'

; and implements IRange.

; The IRange interface includes:

; - in-range? : Number -> Boolean

;   determine if the given number is in this range

; - union : Range -> Range

;   produce the range containing this and the given range

(define-class range%

(fields lo hi)

(check-expect ((range% 0 1) . in-range? 0) true)

(check-expect ((range% 0 1) . in-range? 1) false)

(define (in-range? n)

(and (>= n (send this lo)) (< n (send this hi))))

(define (union r)

(union-range% this r)))

; Part 2:

; A Range is one of

; - (new range% Number Number)

;   Interp: represents the range between ‘lo' and ‘hi'

;           including ‘lo', but *not* including ‘hi'

; - (new hi-range% Number Number)

;   Interp: represents the range between ‘lo' and ‘hi'

;           including ‘hi', but *not* including ‘lo'

; and implements IRange.

(define-class hi-range%

(fields lo hi)

(check-expect ((hi-range% 0 1) . in-range? 0) false)

(check-expect ((hi-range% 0 1) . in-range? 0.5) true)

(check-expect ((hi-range% 0 1) . in-range? 1) true)

(define (in-range? n)

(and (> n (send this lo)) (<= n (send this hi))))

(define (union r)

(union-range% this r)))

; Part 3:

; A Range is one of

; - (new range% Number Number)

;   Interp: represents the range between ‘lo' and ‘hi'

;           including ‘lo', but *not* including ‘hi'

; - (new hi-range% Number Number)

;   Interp: represents the range between ‘lo' and ‘hi'

;           including ‘hi', but *not* including ‘lo'

; - (new union-range% Range Range)

;   Interp: including all the numbers in both ranges

; and implements IRange.

(define-class union-range%

(fields left right)

(define (in-range? n)

(or ((send this left) . in-range? n)

((send this right) . in-range? n)))

(define (union r)

(union-range% this r)))

(define r1 (range% 0 1))

(define r2 (hi-range% 0 1))

(define r3 (range% 2 4))

; union + in-range? test

(check-expect (r1 . union r2 . union r3 . in-range? 3)

true)

; testing all the union methods

(check-expect (r1 . union r2 . in-range? 1) true)

(check-expect (r2 . union r1 . in-range? 0) true)

33.4 Solution: Zombie!

This is a solution for the Zombie! exercise.

#lang class/0

(require 2htdp/image)

(require class/universe)

; A Zombie is one of:

; - Undead

; - Dead

; implements Point and:

; - move-toward : Player -> Zombie

; - eat-zombie-brains? : Zombie -> Boolean

; - eat-player-brains? : Player -> Boolean

; - draw-on : Scene -> Scene

; A Undead is a (new undead% ...)

; A Dead is a (new dead% ...)

; A Zombies is one of:

; - (new emptyz%)

; - (new conz% Zombie Zombies)

; implements

; - draw-on : Scene -> Scene

; A Player is (new player% Posn)

; implements Point and

; - move-toward : Mouse -> Player

; - draw-on : Scene -> Scene

; A Point implements

; - x : -> Number

; - y : -> Number

; A Posn is a (new posn% Number Number)

; implements Point and

; - move-toward : Point -> Posn

; - draw-on/image : Image Scene -> Scene

; A Mouse is a (new mouse% Number Number)

; implements

; draw-on : Scene -> Scene

; Draws this mouse on the scene

(define PLAYER-VELOCITY 3)

(define ZOMBIE-VELOCITY 1)

(define PLAYER-RADIUS 10)

(define ZOMBIE-RADIUS 10)

(define-class emptyz%

(define (draw-on scn) scn)

(define (move-toward player) this)

(define (any-eating-player-brains? player) false)

(define (any-eating-zombie-brains? zombie) false)

(define (kill-any-touching) this)

(define (kill-any-touching/a zs) zs))

(define-class conz%

(fields first rest)

(define (draw-on scn)

(send (send this first) draw-on

(send (send this rest) draw-on scn)))

(define (move-toward player)

(new conz%

(send (send this first) move-toward player)

(send (send this rest) move-toward player)))

(define (any-eating-player-brains? player)

(or (send (send this first) eat-player-brains? player)

(send (send this rest) any-eating-player-brains? player)))

(define (any-eating-zombie-brains? zombie)

(or (send (send this first) eat-zombie-brains? zombie)

(send (send this rest) any-eating-zombie-brains? zombie)))

(define (kill-any-touching)

(send this kill-any-touching/a (new emptyz%)))

(define (kill-any-touching/a zs)

(local [(define first-z (send this first))

(define rest-z (send this rest))]

(cond [(or (send zs any-eating-zombie-brains? first-z)

(send rest-z any-eating-zombie-brains? first-z))

(send rest-z kill-any-touching/a (new conz% (send first-z kill) zs))]

[else

(send rest-z kill-any-touching/a (new conz% first-z zs))]))))

; A Undead is a (new undead% Posn) implements Zombie

(define-class undead%

(fields p)

; - move-toward : Player -> Zombie

; - eat-zombie-brains? : Zombie -> Boolean

; - eat-player-brains? : Player -> Boolean

(define (x) (send (send this p) x))

(define (y) (send (send this p) y))

(check-expect (send (new undead% (new posn% 10 20)) draw-on (empty-scene 100 100))

(place-image (circle ZOMBIE-RADIUS "solid" "red")

10 20

(empty-scene 100 100)))

(define (draw-on scn)

(send (send this p) draw-on/image (circle ZOMBIE-RADIUS "solid" "red") scn))

(check-expect (send (new undead% (new posn% 0 0)) move-toward

(new player% (new posn% 0 10)))

(new undead% (new posn% 0 ZOMBIE-VELOCITY)))

(check-expect (send (new undead% (new posn% 0 0)) move-toward

(new player% (new posn% 10 0)))

(new undead% (new posn% ZOMBIE-VELOCITY 0)))

; move-toward : Player -> Zombie

; Move this player ZOMBIE-VELOCITY units toward the given player.

(define (move-toward player)

(new undead% (send (send this p) move-toward player ZOMBIE-VELOCITY)))

; eat-player-brains? : Player -> Boolean

(define (eat-player-brains? player)

(< (send (send this p) dist player)

(+ ZOMBIE-RADIUS PLAYER-RADIUS)))

; eat-zombie-brains? : Zombie -> Boolean

(define (eat-zombie-brains? zombie)

(< (send (send this p) dist zombie)

(* 2 ZOMBIE-RADIUS)))

; kill : -> Dead

(define (kill)

(new dead% (send this p))))

; A Dead is a (new dead% ...) implements Zombie

(define-class dead%

(fields p)

(define (x) (send (send this p) x))

(define (y) (send (send this p) y))

; - move-toward : Player -> Zombie

; - eat-zombie-brains? : Zombie -> Boolean

; - eat-player-brains? : Player -> Boolean

(check-expect (send (new dead% (new posn% 10 20)) draw-on (empty-scene 100 100))

(place-image (circle ZOMBIE-RADIUS "solid" "gray")

10 20

(empty-scene 100 100)))

(define (draw-on scn)

(send (send this p) draw-on/image (circle ZOMBIE-RADIUS "solid" "gray") scn))

(check-expect (send (new dead% (new posn% 0 0)) move-toward

(new player% (new posn% 0 10)))

(new dead% (new posn% 0 0)))

(check-expect (send (new dead% (new posn% 0 0)) move-toward

(new player% (new posn% 10 0)))

(new dead% (new posn% 0 0)))

(define (move-toward player)

this)

; eat-player-brains? : Player -> Boolean

(define (eat-player-brains? player)

(< (send (send this p) dist player)

(+ ZOMBIE-RADIUS PLAYER-RADIUS)))

; eat-zombie-brains? : Zombie -> Boolean

(define (eat-zombie-brains? zombie)

(< (send (send this p) dist zombie)

(* 2 ZOMBIE-RADIUS)))

; kill : -> Dead

(define (kill)

this))

(define-class posn%

(fields x y)

; Move this position toward that one at given velocity.

; move-toward : Point Number -> Posn

(define (move-toward that velocity)

(local [(define delta-x (- (send that x) (send this x)))

(define delta-y (- (send that y) (send this y)))

(define move-distance

(min velocity

(max (abs delta-x)

(abs delta-y))))]

(cond [(< (abs delta-x) (abs delta-y))

; move along y-axis

(cond [(positive? delta-y)

(send this move 0 move-distance)]

[else

(send this move 0 (- move-distance))])]

[else

; move along x-axis

(cond [(positive? delta-x)

(send this move move-distance 0)]

[else

(send this move (- move-distance) 0)])])))

; move : Number Number -> Posn

(define (move delta-x delta-y)

(new posn%

(+ (send this x) delta-x)

(+ (send this y) delta-y)))

; draw-on/image : Image Scene -> Scene

(define (draw-on/image img scn)

(place-image img

(send this x)

(send this y)

scn))

; dist : Point -> Number

; Compute the distance between this posn and that point.

(define (dist that)

(sqrt (+ (sqr (- (send that y) (send this y)))

(sqr (- (send that x) (send this x)))))))

(define-class player%

(fields p)

(define (x) (send (send this p) x))

(define (y) (send (send this p) y))

; move-toward : Mouse -> Player

; Move this player PLAYER-VELOCITY units toward the given mouse.

(define (move-toward mouse)

(new player%

(send (send this p) move-toward mouse PLAYER-VELOCITY)))

(check-expect (send (new player% (new posn% 10 20)) draw-on (empty-scene 100 100))

(place-image (circle PLAYER-RADIUS "solid" "green")

10 20

(empty-scene 100 100)))

(define (draw-on scn)

(send (send this p) draw-on/image (circle PLAYER-RADIUS "solid" "green") scn)))

(check-expect (send (new posn% 0 0) move-toward (new posn% 0 0) 100)

(new posn% 0 0))

(check-expect (send (new posn% 0 0) move-toward (new posn% 100 0) 50)

(new posn% 50 0))

(check-expect (send (new posn% 0 0) move-toward (new posn% 0 100) 50)

(new posn% 0 50))

(check-expect (send (new posn% 0 0) move-toward (new posn% 100 100) 50)

(new posn% 50 0))

(check-expect (send (new posn% 0 0) move-toward (new posn% 100 101) 50)

(new posn% 0 50))

(check-expect (send (new posn% 0 0) move-toward (new posn% 101 100) 50)

(new posn% 50 0))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 0 0))

(new player% (new posn% 0 0)))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 100 0))

(new player% (new posn% PLAYER-VELOCITY 0)))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 0 100))

(new player% (new posn% 0 PLAYER-VELOCITY)))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 100 100))

(new player% (new posn% PLAYER-VELOCITY 0)))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 100 101))

(new player% (new posn% 0 PLAYER-VELOCITY)))

(check-expect (send (new player% (new posn% 0 0)) move-toward (new mouse% 101 100))

(new player% (new posn% PLAYER-VELOCITY 0)))

(define-class mouse%

(fields x y)

; draw-on : Scene -> Scene

; Draw this mouse on the scene

(check-expect (send (new mouse% 10 20) draw-on (empty-scene 100 100))

(place-image (square 5 "solid" "red")

10

20

(empty-scene 100 100)))

(define (draw-on scn)

(place-image (square 5 "solid" "red")

(send this x)

(send this y)

scn)))

; A ZombieApocalypse (ZA) is a (new za% Zombies Player Mouse)

; implements

; - on-tick : -> ZA

; - to-draw : -> Scene

; - on-mouse : MouseEvent Number Number -> ZA

; - stop-when : -> Boolean

(define WIDTH 200)

(define HEIGHT 200)

(define-class za%

(fields zombies player mouse)

; on-tick : -> ZA

(define (on-tick)

(new za%

(send (send (send this zombies) kill-any-touching) move-toward (send this player))

(send (send this player) move-toward (send this mouse))

(send this mouse)))

; to-draw : -> Scene

(define (to-draw)

(send (send this zombies) draw-on

(send (send this player) draw-on

(send (send this mouse) draw-on

(empty-scene WIDTH HEIGHT)))))

; on-mouse : Number Number MouseEvent -> ZA

(define (on-mouse mx my me)

(new za%

(send this zombies)

(send this player)

(new mouse% mx my)))

; stop-when : -> Boolean

(define (stop-when)

(send (send this zombies) any-eating-player-brains?

(send this player))))

(define world0

(new za%

(new conz%

(new undead% (new posn% 60 60))

(new conz%

(new undead% (new posn% 100 100))

(new emptyz%)))

(new player% (new posn% 0 0))

(new mouse% 0 0)))