Finger Exercises

Matthias Felleisen

#| ============================================================================
The class of lists that contain X's is defined as follows: 

(listof X) is one of: 
 empty 
 (cons X (listof X))
|#

#| ============================================================================
The class of association lists is defined as follows: 

(A-list X) is one of: 
 empty 
 (cons (list Symbol X) (A-list X))
|#

Develop the following functions on assoication lists:

1. domain : (A-list X) -> (listof Symbol), which consumes an assoication list and which produces the list of symbols that are the first components of the associations.
2. lookup : Symbol (A-list X) -> X, which consumes a symbol (s) and an association list over X and which produces an X that corresponds to s. Assume that s is in the domain of the given A-list.
3. update : Symbol X (A-list X) -> (A-list X); it consumes a symbol s, an item x from X, and an association list a-l over X. It produces an association list over X like a-l but with pairs of shape (list s _) replaced with (list s x).

The class of s-lists is defined as follows:

S-list is one of: 
 empty 
 (cons S S-list)

S is: 
 (make-s Symbol Number)

(define-struct s (name value))

4. Develop the function

  ;; s-lookup : Symbol S-list -> Number
  ;; to extract the (first) number asociated with s in s-l
  ;; assume: s occurs in the domain of s-l
  (define (s-lookup s s-l) ...)

Scheme provides the following higher-order primitives:

   map  : (X -> Y) (listof X) -> (listof Y)
   map  : (X Z -> Y) (listof X) (listof Z) -> (listof Y)
  
   assq : Symbol (listof (cons Symbol X)) -> (union false (cons Symbol X))
   assf : (X -> Boolean) (listof X) -> (union false X)

   andmap : (X -> Boolean) (listof X) -> Boolean

5. Use these primitives to re-implement domain, lookup, and s-lookup.

6. Develop the function okay, which consumes an s-list and determines whether all numbers in the s-list are greater or equal to 0.

Consider the following data definition:

Mamboo is one of:
 (make-zero Symbol)
 (make-one  Symbol Mamboo)
 (make-two  Mamboo Mamboo)

(define-struct zero (name))
(define-struct one (name body))
(define-struct two (lhs rhs))

7. Develop the function

  ;; collect-all : Mamboo -> (listof Symbol)
  ;; to determine the symbols that occur in m 
  (define (collect-all m) ...)

Question: is the problem statement ambiguous? If so, show two different implementations for collect-all. If not, argue succinctly why the statement is unambiguous.

The homework is due on Monday 1 October 2001 before class.

Expected size: 200 lines