Scheme Programming Assignment


Assigned: 10/8/96
Due: 10/17/96 (Thursday by midnight)
Submission procedure: via email to echris@cs

Write the code for this assignment as succinctly and readably as possible. All codes must be strictly functional (i.e., none of your code should produce side-effects). You need to write 4 functions (plus an extra credit function if you like). They are of equal weight (grading-wise).

Make sure your code works in MIT Scheme, as I will be executing it in that interpreter. Check out the Scheme/Lisp Resources page to get started with MIT Scheme.


  1. In quiz section we defined a Scheme function that builds and returns a list of decreasing numbers. For example,

        > (build-list 5) => (5 4 3 2 1)
    
    Write a Scheme function called build-list-increasing that builds and returns a list of increasing numbers. For example,

        > (build-list-increasing 5) => (1 2 3 4 5)
    
    My implementation of build-list-increasing is about 5 lines. Don't use the built-in reverse function in your solution.

  2. An association list (a-list) associates a key with a value. The basic operations on an a-list are alist-add and alist-find, defined below. The function alist-add takes a key, a value, and an a-list and returns a new a-list with the key associated with value. The function alist-find takes a key and an a-list and returns the value associated with key in the a-list that it was passed.

    We will represent an a-list by a list of two item lists. The first item in each sublist is the key, and the second item is the value associated with this key. Consider the following list. It associates the symbol RICHIE with SUCCESSFUL-DIRECTOR, FONZIE with COOL and RALPH-MALPH with DORK.

        '((RICHIE SUCCESSFUL-DIRECTOR) (FONZIE COOL) (RALPH-MALPH DORK))
    
    Below are some functions for adding associations to an a-list and looking up the value associated with a particular key.

        ; alist-add - return alist augmented with key/val
        (define (alist-add key val alist)
          (cons (list key val) alist))
    
        ; alist-first-key - return first key in alist x
        (define (alist-first-key x) (car (car x)))
    
        ; alist-first-val - return first value in alist x
        (define (alist-first-val x) (car (cdr (car x))))
    
        ; alist-find - return first value associated with key in alist
        (define (alist-find key alist)
          (if (null? alist) ()
              (if (eqv? key (alist-first-key alist)) (alist-first-val alist)
                  (alist-find key (cdr alist)))))
    
    Here is some code to use the above code.

        > (define happy-days 
                  (alist-add 'RICHIE 
                             'SUCCESSFUL-DIRECTOR
                             (alist-add 'FONZIE
                                        'COOL
                                        (alist-add 'RALPH-MALPH
                                                   'DORK
                                                   ()))))
        > (alist-find 'RALPH-MALPH happy-days) => 'DORK
        > (alist-find 'MR-CUNNINGHAM happy-days) => ()
    
    1. When new associations are added to an a-list (via alist-add) they effectively "replace" previous associations for the same key, because alist-find stops at the first key match. Write a new version of alist-add (call it alist-add-replace) that prevents duplicates keys from appearing in the returned a-list. The new function should take the same arguments as alist-add, and it should return a new, duplicate-key-free a-list.

      My implementation is about 6 lines long.

    2. Write a function called alist-remove. This function takes a key and an a-list and returns a copy of the a-list minus the associations for key. Here is an example of how it works.
          > (alist-remove 'fonzie happy-days)
          => ((richie successful-director) (ralph-malph dork))
      
      My implementation is about 5 lines long.

    3. Write a function (call it alist-keys) that takes a value and an a-list and returns a list of all the keys to which the value is associated in the a-list. Here is an example of the code in action.
          > (alist-keys 22 '((a 11) (b 22) (c 22))) => (b c)
      
      My implementation is about 5 lines long.

    4. EXTRA CREDIT: Write a function that applies a caller provided function to each associate in an a-list and builds a list from the return values of each application of the function. Call this function alist-map. Here is an example of this code in use.
          > (alist-map '((a 1) (b 2) (c 3)) (lambda (k v) v)) => (1 2 3)
          > (alist-map '((a 1) (b 2) (c 3)) (lambda (k v) k)) => (a b c) 
      
      My implementation is about 4 lines long.

Make sure you understand how each piece of code is to work before you start writing.


echris@cs.washington.edu (10/8/96)