Exam 4: Advanced Scheming

Topics: Association lists, list recursion, algorithm analysis, lists

As you may recall, an association list is a list of key/value pairs. It's easy to add a key/value pair to an association list. It's a bit harder to remove key/value pairs.

a. Write a procedure, (assoc-list-remove alist key), that removes all of the key/value pairs with a matching key from the association list.

;;; Procedure:
;;;   assoc-list-remove
;;; Parameters:
;;;   alist, an association list
;;;   key, a value
;;; Purpose:
;;;   Remove *all* entries with the specified key from the list.
;;; Produces:
;;;   newlist, an association list
;;; Preconditions:
;;;   alist has the standard form of an association list, a list
;;;     of key/value pairs.
;;; Postconditions:
;;;   For all k not equal to key, (assoc k newlist) = (assoc k alist)
;;;   (assoc key newlist) = #f.

Here's an example.

> (define sample
    (list (list "TUT100" "Joy")
          (list "CSC151" "Functional Problem Solving")
          (list "CSC207" "Algorithms and Objects")
          (list "TEC154" "Evolution of Technology")
          (list "TUT100" "Time")
          (list "TUT100" "Failure")))
> (assoc "TUT100" sample)
'("TUT100" "Joy")
> (assoc "TUT100" (cdr sample))
'("TUT100" "Time")
> (assoc-list-remove sample "TUT100")
'(("CSC151" "Functional Problem Solving")
  ("CSC207" "Algorithms and Objects")
  ("TEC154" "Evolution of Technology"))
> (assoc-list-remove sample "CSC151")
'(("TUT100" "Joy")
  ("CSC207" "Algorithms and Objects")
  ("TEC154" "Evolution of Technology")
  ("TUT100" "Time")
  ("TUT100" "Failure"))

b. How many calls will your procedure make to cons, car, and cdr for each of the following?

i. A list of N elements in which the key does not appear.

ii. A list of N elements in which the key appears only in the first element.

iii. A list of N elements in which the key appears only in the last element.

iv. A list of N elements in which the key appears in every element.

v. A list of N elements in which the key appears in every-other element.

Topics: Association lists, vectors, vector recursion, algorithm analysis

An associative vector is much like an association list, except that we store the key/value pairs in a vector, rather than a list, that we permit the vector to contain null values at the end, and that we can change the vector “in place”.

Here's a sample session with an associative vector.

> (define sample
    (vector (list "TUT100" "Joy")
            (list "CSC151" "Functional Problem Solving")
            (list "CSC207" "Algorithms and Objects")
            (list "TEC154" "Evolution of Technology")
            (list "TUT100" "Time")
            (list "TUT100" "Failure")
            null
            null
            null))
> sample
'#(("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("TEC154" "Evolution of Technology")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ()
   ()
   ())
> (avec-get sample "CSC151")
'("CSC151" "Functional Problem Solving")
> (avec-get sample "TUT100")
'("TUT100" "Joy")
> (avec-get sample "CSC161")
#f
> (avec-set! sample "CSC161" (list "Imperative Problem Solving"))
#t
> (avec-get sample "CSC161")
'("CSC161" "Imperative Problem Solving")
> sample
'#(("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("TEC154" "Evolution of Technology")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ("CSC161" "Imperative Problem Solving")
   ()
   ())
> (avec-get sample "CSC207")
'("CSC207" "Algorithms and Objects")
> (avec-set! sample "CSC207" (list "Algorithms and Object-Oriented Design"))
#t
> (avec-get sample "CSC207")
'("CSC207" "Algorithms and Object-Oriented Design")
> sample
'#(("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Object-Oriented Design")
   ("TEC154" "Evolution of Technology")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ("CSC161" "Imperative Problem Solving")
   ()
   ())

It is fairly straightforward to set and get elements from an associative vector.

;;; Procedure:
;;;   avec-set!
;;; Parameters:
;;;   avec, an associative vector
;;;   key, a Scheme value
;;;   value, a Scheme value
;;; Purpose:
;;;   Makes sure that the entry for key returns value.
;;; Produces:
;;;   success, a Boolean value
;;; Preconditions:
;;;   avec has the standard form for associative vectors.
;;; Postconditions:
;;;   If avec contains any null entries, then success is true.
;;;   If success is true, then (avec-get avec key) returns (cons key value).
;;;   Otherwise, (avec-get avec key) returns #f.
(define avec-set!
  (lambda (avec key value)
    (let kernel ([i 0])
      (cond
        [(equal? i (vector-length avec))
         #f]
        [(null? (vector-ref avec i))
         (vector-set! avec i (cons key value))
         #t]
        [(equal? key (car (vector-ref avec i)))
         (vector-set! avec i (cons key value))
         #t]
        [else
         (kernel (+ i 1))]))))

;;; Procedure:
;;;   avec-get
;;; Parameters:
;;;   avec, an associative vector
;;;   key, a value
;;; Purpose:
;;;   Finds the first entry in avec with the given key.
;;; Produces:
;;;   entry, either a key/value pair or #f
;;; Preconditions:
;;;   avec has the standard form for associative vectors.
;;; Postconditions:
;;;   If there is an i s.t. (equal? key (car (vector-ref avec i))),
;;;     then entry is (vector-ref avec i)
;;;   Otherwise, entry is #f
(define avec-get
  (lambda (avec key)
    (let kernel ([i 0])
      (cond
        [(equal? i (vector-length avec))
         #f]
        [(null? (vector-ref avec i))
         #f]
        [(equal? key (car (vector-ref avec i)))
         (vector-ref avec i)]
        [else
         (kernel (+ i 1))]))))

Since we've just figured out how to remove elements from an association list, we should figure out something similar for an associative vector.

a. Write a procedure, (avec-remove! vec key), that removes all of the key/value pairs with a matching value from the vector.

;;; Procedure:
;;;   avec-remove!
;;; Parameters:
;;;   avec, an associative vector
;;;   key, a value
;;; Purpose:
;;;   Remove *all* entries with the specified key from the list.
;;; Produces:
;;;   [Nothing; called for the side effect.]
;;; Preconditions:
;;;   avec has the standard form of an associative vector.
;;; Postconditions:
;;;   For all k not equal to key, (avec-get avec k) remains the same
;;;   (avec-get avec key) = #f.

Here's an extended example that shows removal in the middle, at the front, at the back, and at multiple positions.

> (define sample
    (vector (list "CSC105" "The Digital Age")
            (list "TUT100" "Joy")
            (list "CSC151" "Functional Problem Solving")
            (list "CSC207" "Algorithms and Objects")
            (list "TEC154" "Evolution of Technology")
            (list "TUT100" "Time")
            (list "TUT100" "Failure")
            (list "MAT115" "Statistics")
            null
            null
            null))
> sample
'#(("CSC105" "The Digital Age")
   ("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("TEC154" "Evolution of Technology")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ("MAT115" "Statistics")
   ()
   ()
   ())
> (avec-remove! sample "TEC154")
> sample
'#(("CSC105" "The Digital Age")
   ("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ("MAT115" "Statistics")
   ()
   ()
   ()
   ())
> (avec-remove! sample "CSC999")
> sample
'#(("CSC105" "The Digital Age")
   ("TUT100" "Joy")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("TUT100" "Time")
   ("TUT100" "Failure")
   ("MAT115" "Statistics")
   ()
   ()
   ()
   ())
> (avec-remove! sample "TUT100")
> sample
'#(("CSC105" "The Digital Age")
   ("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("MAT115" "Statistics")
   ()
   ()
   ()
   ()
   ()
   ()
   ())
> (avec-remove! sample "CSC105")
> sample
'#(("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ("MAT115" "Statistics")
   ()
   ()
   ()
   ()
   ()
   ()
   ()
   ())
> (avec-remove! sample "MAT115")
> sample
'#(("CSC151" "Functional Problem Solving")
   ("CSC207" "Algorithms and Objects")
   ()
   ()
   ()
   ()
   ()
   ()
   ()
   ()
   ())

b. How many calls will your procedure make to vector-ref, and vector-set! for each of the following?

i. A vector of N elements in which the key does not appear.

ii. A vector of N elements in which the key appears only in the first element.

iii. A vector of N elements in which the key appears only in the last element.

iv. A vector of N elements in which the key appears in every element.

v. A vector of N elements in which the key appears in every-other element.

Topics: Higher-order procedures, recursion, code reading, documentation

Consider the following procedure definition.

(define iowa
  (lambda (illinois michigan)
    (letrec ([indiana (lambda (south-dakota north-dakota)
                        (if (illinois south-dakota north-dakota) south-dakota north-dakota))]
             [minnesota (lambda (wisconsin)
                    (cond [(null? (cdr wisconsin)) (list (list (car wisconsin) (car wisconsin)))]
                          [(null? (cddr wisconsin)) (list wisconsin)]
                          [else (cons (list (car wisconsin) (cadr wisconsin))
                                      (minnesota (cddr wisconsin)))]))])
      (if (null? (cdr michigan))
          (car michigan)
          (iowa illinois (map (l-s apply indiana) (minnesota michigan)))))))

Figure out what this procedure does, and then do the following.

a. Rename the procedure and the parameters so they will make sense to the reader, and write 6P-style documentation for this procedure.

b. Explain how this procedure works. A correct explanation will describe the high-level steps to compute a result, not just restate the code in prose.

Topics: Files, file recursion, read-char.

We have discussed two different ways to read files with Scheme: The read procedure reads a Scheme value (e.g. "a string" or the number 42) from a file, while the read-char parameter reads a single character. The read-char function allows us to deal with raw text files, this isn't always convenient; when dealing with raw text files, it is often useful to read them word-by-word rather than one character at a time.

Write and document a procedure (read-word input-port) that reads an entire word from an open file. A word is a sequence of alphabetic and numeric characters separated by spaces, punctuation, or other symbols. You can check if a character is alphabetic or numeric using char-alphabetic? and char-numeric?, respectively.

The following example uses of read-word may be useful in developing your approach. The contents of somewords.txt are:

Look! This file has the
best words spread out
over 3 lines.

Using this file as input, the following calls to read-word show how your implementation should combine sequences of characters from the file into words. Note that the second call to read-word skips over all non-alphanumeric characters (both the exclamation point and space) to find the beginning of the next word.

> (define myport (open-input-file "/home/curtsinger/CSC151/somewords.txt"))
  
> (read-word myport)
"Look"

> (read-word myport)
"This"

> (read-word myport)
"file"

> (read-word myport)
"has"

> (read-word myport)
"the"

> (read-word myport)
"best"

> (read-word myport)
"words"

> (read-word myport)
"spread"

> (read-word myport)
"out"

> (read-word myport)
"over"

> (read-word myport)
"3"

> (read-word myport)
"lines"

> (read-word myport)
#<eof>

> (close-input-port myport)

As the example suggests, when you reach the end of the file, you should return the end-of-file object.

The somewords.txt file is relatively simple. When you are ready for more of a challenge, try /home/rebelsky/Desktop/morewords.txt, which contains the following text.

SamR (who often writes parenthetical remarks)
worries that some 
students
will
think
"I can just use the read procedure."
They will be wrong.

Topics: List recursion, higher-order procedures.

As you may recall, when we first considered recursive helper procedures, our motivation was to correctly subtract lists of numbers from left to right. In particular, we wrote a procedure similar to the following:

(define difference
  (lambda (numbers)
    (let kernel ([difference-so-far (car numbers)]
                 [remaining (cdr numbers)])
         (if (null? remaining)
	     difference-so-far
	     (kernel (- difference-so-far (car remaining)) (cdr remaining))))))

This pattern is useful for more than just computing differences. It is so useful that computer scientists have generalized it to a procedure often called left-reduce. left-reduce takes two parameters: proc, a binary procedure that combines each element of the list with the answer so far, and lst, the list itself.

Here are some examples of left-reduce in action. We've shown the sequence of calls to the kernel so you can see how it would work.

> (left-reduce + (list 100 4 5))
(kernel 100 (4 5))
(kernel 104 (5))
(kernel 109 ())
109
> (left-reduce - (list 100 4 5))
(kernel 100 (4 5))
(kernel 96 (5))
(kernel 91 ())
91
> (left-reduce - (list 10 4 3 2 1 ))
(kernel 10 (4 3 2 1))
(kernel 6 (3 2 1))
(kernel 3 (2 1))
(kernel 1 (1))
(kernel 0 ())
0
> (left-reduce (lambda (s1 s2) (string-append s1 " " s2)) (list "My" "bonnie" "lies" "over" "the" "ocean"))
(kernel "My" ("bonnie" "lies" "over" "the" "ocean"))
(kernel "My bonnie" ("lies" "over" "the" "ocean"))
(kernel "My bonnie lies" ("over" "the" "ocean"))
(kernel "My bonnie lies over" ("the" "ocean"))
(kernel "My bonnie lies over the" ("ocean"))
(kernel "My bonnie lies over the ocean" ())
"My bonnie lies over the ocean"
> (left-reduce (lambda (s1 s2) (string-append s2 " " s1)) (list "My" "bonnie" "lies" "over" "the" "ocean"))
(kernel "My" ("bonnie" "lies" "over" "the" "ocean"))
(kernel "bonnie My" ("lies" "over" "the" "ocean"))
(kernel "lies bonnie My" ("over" "the" "ocean"))
(kernel "over lies bonnie My" ("the" "ocean"))
(kernel "the over lies bonnie My" ("ocean"))
(kernel "ocean the over lies bonnie My" ())
"ocean the over lies bonnie My"

Implement, but do not document, left-reduce.

Topics: Pairs, deep recursion

As you may recall, we sometimes refer to the two-element-box created by the cons procedure as a “pair”. It can be very useful to identify just how many pairs appear in a structure, in part because it tells us a bit about the effort required to make the structure.

Define and test a procedure, (count-pairs value), that takes as input a Scheme value (e.g., a pair structure or list) and determines how many pairs (cons cells) appear in that structure.

For example,

> (count-pairs null)
0
> (count-pairs 5)
0
> (count-pairs (cons 5 null))
1
> (count-pairs (list 5))
1
> (count-pairs (cons null 5))
1
> (count-pairs (cons (cons 'a 'b) 'c))
2
> (count-pairs (list 1 2 3 4 5))
5
> (count-pairs (list null null null))
3
> (count-pairs (list (list 1 2 3) (list 4 5)))
7

As the examples above suggest, you need to look within lists to determine if their individual elements themselves contains pairs. (You may find that this happens automatically as you handle non-lists.) However, you need not look within vectors to see if they contain any pair structures.

> (count-pairs (vector (list 1)))
0