Exam#1 Solutions -- Problem 3

1998 Spring

(30pts)

Write a data description for a <list-of-doors> (where <door>s will be defined below).

A <list-of-doors> is either

null, or
(cons d lod),
where d is a <door>, and lod is a <list-of-doors>.

Write a template for a <list-of-doors>-handling function, assuming you will have a <door>-handling function.

;; lod-handler: <list-of-door> --> ??
;; A template, following from the data definition.
;;
; (define lod-handler
;   (lambda (lod)
;     (cond [(null? lod) ...]
;           [(cons? lod) ...(door-handler (first lod))...
;                        ...(lod-handler  (rest  lod))...])))

Of course, you could have used else instead of asking cons?; asking the question not only lets you re-order the cases with impunity, but in real life lets you add an error clause, [else (error 'lod-handler "Unexpected argument ~s~n" lod)].

There are three types of <door> s, depending on what's on the other side: Either a room (which has a name, but nothing else), or a hallway (which has a name and a <list-of-doors>), or the outside (which has no further information). Write a reasonable data description for a <door>, along with any accompanying define-structs.

A <door> is either

(make-room name), or
(make-hallway name lod), or
(make-outside),

where name is a symbol and lod is a <list-of-doors>.

To get these constructors constructors known to Scheme, we write

(define-struct room (name))
(define-struct hallway (name lod))
(define-struct outside ())

For the last case we could have used a constant symbol (perhaps 'outdoors), although it's perfectly fine to have a structure with zero fields. The zero-argument structure is preferable because

it generates the predicate outside? automatically, and more importantly
if I later decide that there is some internal structure to the outside, it minimizes the code I would need to modify.

Write a template for a <door>-handling function; remember to write in any appropriate recursive calls.

;; door-handler:  --> ??
;; A template, following from the data definition.
;;
; (define door-handler
;   (lambda (d)
;     (cond [(room? d)    ...(room-name d)]
;           [(hallway? d) ...(hallway-name d)...
;                         ...(lod-handler (hallway-lod d))...]
;           [(outside? d) ...]
;           [else (error 'door-handler "Unknown type of door, ~s~n" d)])))

Write the function can-escape?, which takes a <door> and indicates whether it is possible to reach the outside. (Include the contract for each function you write.)

We flesh out the templates for <door> and <list-of-doors>. A natural way to represent whether or not we can reach the outside is by returning a boolean value. (It is also acceptable to return tokens like 'can-get-out and 'locked-in. Notice though that in Scheme, it is a convention that functions whose names end in ? always return boolean.)

;; can-escape?:  --> boolean
;; Does the door d lead to the outside?
;;
 (define door-handler
   (lambda (d)
     (cond [(room? d)    #f]
           [(hallway? d) (hallway-leads-out? (hallway-lod d))]
           [(outside? d) #t]
           [else (error 'door-handler "Unknown type of door, ~s~n" d)])))

;; hallway-leads-out?: <list-of-doors> --> boolean
;; Can we get outside via any door in the hallway?
;;
 (define hallway-leads-out?
   (lambda (lod)
     (cond [(null? lod) #f]
           [(cons? lod) (or (door-handler (first lod))
                            (hallway-leads-out? (rest  lod)))]
           [else (error 'hallway-leads-out "bad list-of-doors ~s~n" lod)])))

A common bug was to not follow the template, and inside the <list-of-doors> handler, start dissecting the cases of the first door. This usually resulted in a bug where if the first door were a hallway, the answer just recurred on that hallway, ignoring all the rest of the rooms in the original input list.