CSC151, Class 27: Association Lists

Overview:
* Storing collections of information
* The assoc procedure
* Lab

Notes:
* Read Vectors.
* List of three books NOW!
  (list "author-last" "author-first" "title"
        (list "adj1" "adj2" "adj3" "adj4" "adj5"))
* No more CS151 homework before break!
* Guest speaker on Friday.
* Questions on homework 3?
* Writing listp?

listp? determines if a value is a list
It's just like list?, except that we can't define it with
(define listp? list?)

A list is ...
  (1) null
  (2) (cons anything a-list)

How do we write listp?

(define listp?
  (lambda (val) 
     (if (null? val) #t
         ; See if val is "cons of anything and a list"
         (if (pair? val) 
             (if (listp? (cdr val)) #t #f)
             #f))))

(define listp?
  (lambda (val)
     (or (null? val)
         (and (pair? val)
              (listp? (cdr val))))))

----------------------------------------

Observation: Most computing deals with processing collections
of information

How can we represent information about a single book?
  Author Title ISBN Price
Strategy one: Carefully place them all together in a string, use
  some character in a string as a separator.
It might be perhaps less than pleasant to try to extract the
  different parts of the information about the book.
  "It would suck big time"

Strategy Two: Shove 'em together in a list


How do we deal with multiple books?
Build a list of lists.

We might want to:
* search for author
* search for title
* search for ISBN
* search for all books above a certain price
* arrange it alphabetically by author or title
* arrange it numerically by price
* arrange it ??? by ISBN
* compare individual elements

* What does search return?
  + A single element
  + A list of elements

Scheme provides three built-in procedures for the "search for one
element" task.

(assoc val list-of-lists)
  returns the first element list whose car is equal? to val

assq
assv

NO REFLECTION