2008 MIDTERM ANSWER KEY

1.

a. ((c . d))
b. ()
c. (5)
d. #<procedure>
e. #<struct:promise>
f. (1 1 1)
g. error
h. b
i. 7
j. error
k.

(define (flip f)
    (lambda (x y) (f y x)))

l.

Even something simple like:

(define (ones) (cons 1 (delay (ones))))

would break because delay is no longer a special form, and thus wouldn't halt
evaluation of its argument.  This would cause an infinite loop, since delay
would always try to evaluate its argument.

2. a.

m -> cons
m2 -> cdr
m3 -> car

This implements a somewhat-twisted message-passing object.

b. list?

3.
a. (define (mean lst) (/ (reduce + 0 lst) (length lst))) 
b. (define (small-elements lst)
    (let ((m (mean lst)))
        (filter (lambda (x) (< x m)) lst)))
c. 
(define (square x) (expt x 2))
(define (variance lst)
    (let ((m (mean lst)))
        (/ (reduce (lambda (e a) (+ a (square (- e m)))) 0 lst)
           (length lst))))

4.
a. see b
b.

(define (stream-priority s1 s2)
    (cond ((priority<? (caar s1) (caar s2))
            (cons (cdar s2)
                (delay (stream-priority s1 (force (cdr s2))))))
          ((priority<? (caar s2) (caar s1))
            (cons (cdar s1)
                (delay (stream-priority (force (cdr s1)) s2))))
          ;; equal!
          (else
            (cons (cdar s1)
                (delay (stream-priority s2 (force (cdr s1))))))))

5. 

a.

room-construct
args: name, object
ret: a new room structure with that object in it
contract: since this takes an object, this means that all rooms will have at
least one object

room-add-object
args: room, object
ret: same room, with the object added

room-obj-attributes
args: room, objectname
ret: list of object attributes if object found, #f if nothing found

room-num-objects
args: room
ret: number of objects in the room

b.

map-construct
args: room
ret: new map with the single room in it

map-add-room 
args: map, existing-room, new-room
ret: new map with the existing-room and the new-room connected
contract: existing-room must be in the map, or the same map is returned

map-num-rooms
args: map
ret: number of rooms in the map

map-adj-rooms?
args: map, room1, room2
ret: #t if room1 and room2 are in both the map and adjacent, #f otherwise

c.

#1 -> map-adj-rooms?
#2 -> map-num-rooms
#3 -> room-obj-attributes
#4 -> room-num-objects

d.

room-* objects should be implemented with a dictionary with object names as
the keys and lists of object attributes as the values.

map-* functions could be implemented easily with a graph, similar to what we
had in asst3.  Note that map-*'s interface is slightly more restricted than
the graph interface, because maps have less flexibility than graphs.

6.

a. 
(define (reduce-left f base lst)
  (if (null? lst) 
    base
    (reduce-left f (f base (car lst)) (cdr lst))))

b.
[This question turned out a lot harder than we intended it to be, so we
accepted some incorrect answers that were on the right track.]

(define (running-sum lst)
    (reverse
        (reduce-left 
            (lambda (a e) (cons (+ e (if (null? a) 0 (car a))) a))
            ()
            lst)))

c.
;; flip as defined in # 1k
(define (reduce-left f base lst)
    (reduce-right (flip f) base (reverse lst)))