Scheme Programming Assignment Solutions


This document contains function definitions to implement the first programming assignment. Note that there are more ways to implement these functions than I have shown here. The functions below are good, but I'll bet we could dream up better (and worse) solutions.
  1. PART 1

    Write a Scheme function called build-list-increasing that builds and returns a list of increasing numbers. Here are a couple functions that implement this behavior.

        (define (build-list-increasing x)
          (define (build-list-increasing-helper x max)  
            (if (> x max) ()
    	    (cons x (build-list-increasing-helper (+ 1 x) max))))
          (build-list-increasing-helper 1 x))
    
        (define (build-list-increasing x)
          (if (< x 1) ()
              (append (build-list-increasing2 (- x 1)) (list x))))
    
  2. PART II

    1. Write a new version of alist-add (call it alist-add-replace) that prevents duplicates keys from appearing in the returned a-list. Here are a couple implementations.

          (define (alist-add-replace key val alist)
            (if (null? alist) (list key val)
                (let ((rest (alist-add-replace key val (cdr alist))))
                  (if (eqv? key (alist-first-key alist))
                      (cons (list key val) rest)
                      (cons (car alist) rest)))))
      
          (define (alist-add-replace key val alist)
            (alist-add key val (alist-remove key alist)))
      
    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 implementation.

          (define (alist-remove key alist)
            (if (null? alist) ()
                (let ((rest (alist-remove key (cdr alist))))
                  (if (eqv? key (alist-first-key alist)) 
                      rest
                      (cons (car alist) rest)))))
      
    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 implementation.

          (define (alist-keys val alist)
            (if (null? alist) ()
                (let ((rest (alist-keys val (cdr alist))))
                  (if (eqv? val (alist-first-val alist))
                      (cons (alist-first-key alist) rest)
                      rest))))
      
    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 implementation.

          (define (alist-map alist fn)
            (if (null? alist) ()
                (cons (fn (alist-first-key alist) (alist-first-val alist))
                      (alist-map (cdr alist) fn))))
      

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