CSE 341 -- Scheme Data Abstractions

Using Lists to do Everything

Lists turn out to be incredibly general. Using just lists, symbols, and numbers, we can build just about any interesting data structure.

Setup

We'll be making use of the following helper functions in the below example:

(define (find-if pred? list)
  (cond ((null? list) #f)
        ((pred? (car list)) #t)
        (#f (find-if pred? (cdr list)))))

(define (remove-if test? alist)
  (cond ((null? alist) ())
        ((test? (car alist)) (remove-if test? (cdr alist)))
        (#t (cons (car alist) (remove-if test? (cdr alist))))))

(define (remove-if-not test? alist)
  (remove-if (lambda (x) (not (test? x))) alist))

;; nil is a more readable way to say ()
(define nil ())

Example 1: Table as a list of key-value couples

Using lists to represent tables is very natural. The beautiful thing about Scheme is that we can write table functions (lookup and associate) without having any knowledge of the types of data we are going to be storing in the table. This provides for an extremely high level of abstraction, which is primarily possible through Scheme's dynamic type checking. Ada lets us do this with Generics, C++ with Templates, but neither mechanism is as flexible.

(define *bands* 
 '((seattle-bands (nirvana pearl-jam foo-fighters green-river))
   (la-bands      (black-flag minutemen red-hot-chili-peppers))
   (nz-bands      (bats clean tall-dwarfs))))

;; lookup the value associated with key.  return nil if unassociated.

(define (lookup tbl key)
  (cond ((null? tbl) nil)
	((equal? key (caar tbl)) (cadar tbl))
	(#t (lookup (cdr tbl) key))))

;; return the new table which associates key and value

(define (associate tbl key val)
  (cond ((null? tbl) (list (list key val)))
	((equal? key (caar tbl))) (cons (list key val) (cdr tbl)))
	(T (cons (car tbl) (associate (cdr tbl) key val)))))


(lookup *bands* 'la-bands)    => (black-flag minutemen red-hot-chili-peppers)
(lookup *bands* 'ny-bands)    => nil

What is the running time of these operations? Below we'll see that many dialects of Scheme provide more efficient tables.

Example 2: Binary tree as a list

Lists can be used to represent binary trees as well. We'll use the empty list to represent an empty tree. Otherwise, a tree will consist of a list containing the root, the left subtree, and the right subtree.

(root left-stubtree right-subtree)     ; general form

;; here are the functions that define our Tree ADT.
;; these function make the code more readable, and "hide" the implementation
;; of the tree from the user (although this is not enforced by Scheme)

(define (empty-tree) nil)            ;; constructor: give me an empty tree
(define (make-tree root left right)  ;; constructor: make a tree
  (list root left right))

(define (empty? tree) (null? tree))  ;; predicate:   is the tree empty

(define (root tree) (first tree))   ;; accessor:    give me the root
(define (left tree) (second tree))  ;; accessor:    give me the left subtree
(define (right tree) (third tree))  ;; accessor:    give me the right subtree


;; here are some operations on a BST

(define (bst-insert item tree)
  (cond ((empty? tree) (make-tree item (empty-tree) (empty-tree)))
	;; item is less than the root, so insert into left subtree
	((< item (root tree))
	 (make-tree (root tree) (bst-insert item (left tree)) (right tree)))
	;; item is >= to the root, so insert into right subtree
	(#T
	 (make-tree (root tree) (left tree) (bst-insert item (right tree))))))


(define (bst-lookup item tree)
  (cond ((empty? tree) nil)
	;; we've found the item !
	((equal? (root tree) item) item)
	;; item is less than the root, so look left:
	((< item (root tree)) (bst-lookup item (left tree)))
	;; item is >= the root, so look right:
	(#t (bst-lookup item (right tree)))))

(bst-insert 6 (bst-insert 4 (bst-insert 3 (bst-insert 5 (empty-tree))))) =>
                   (5 (3 nil (4 nil nil)) (6 nil nil))

Example 3: Sets as lists

Using lists to represent sets is very natural. We can write our own ADT functions, like: INTERSECTION, UNION, and MEMBER.

(define (set-member e set) 
  (find-if (lambda (x) (equal? e x)) set))

(define (set-intersection set1 set2)
  (remove-if-not (lambda (x) (set-member x set2)) set1))

(define (set-union set1 set2)
  (append set1 
	  (remove-if (lambda (x) (set-member x set1)) set2)))

Again, these aren't terribly efficient implementations, but they work!

Other complex data structures

It should be easy to imagine how we might implement our other favorite data structures such as stacks, queues, and records using lists.

Arrays

Because random access is not well supported for lists, Scheme provides us with built-in array support (called Vectors). We create new arrays with make-vector and access arrays with vector-ref. We can set fields in the vector with vector-set!. Arrays are accessed starting at zero.

(define foo (make-vector 3))      ;; create an array of length 5
(vector-set! foo 2 'bar)          ;; set an element
foo    => 
   #(#<unspecified> #<unspecified> bar)

(vector-ref foo 5)            => Error! Index out of bounds.
(vector-ref foo 2)            => bar

Records/Structures

One way to fake records is just to use lists, but this doesn't hide the representation from the user. One solution is to define access and constructor functions. Suppose we want to define a point data type:

(define (make-point x y)     ; constructor
  (list x y)) 

(define (x point)            ; accessor
  (first point))

(define (y point)            ; accessor
  (second point))
   
(define (set-x! point x)      ; setters
  (set-car! point x))
   
(define (set-y! point y)
  (set-car! (cdr point) y))

(define (midpoint p1 p2)
  (make-point(/ (+ (x p1) (x p2)) 2)
	     (/ (+ (y p1) (y p2)) 2)))

This allows us to hide the representation of the point, so we could change the internal representation to polar coordinates, while presenting the user with the same interface. Of course, some versions of Scheme provide us with built-in record support. For example, in DrScheme, we can use define-struct. When it evaluates, it creates a constructor, type predicate, getters, and setters...

(define-struct point (x y))

(define p1 (make-point 10 20))           ; constructor
(define p2 (make-point 20 30))
(define p3 (make-point 10 20))

(equal? p1 p2)               => #f
(equal? p1 p3)               => #t
(point? p3)                  => #t       ; type predicate
(point? 'hello)              => #f
(point-x p1)                 => 10       ; getter
(point-y p2)                 => 30
(set-point-x! p1 100)                    ; setter
(point-x p1)                 => 100

Object-oriented programming provides a more sophisticated and flexible way of providing information hiding. Mechanisms for doing OO-style programming abound in Scheme. We'll look at a fully OO language later in the course, called Smalltalk.

Hash Tables

Some versions of Scheme also provide built-in hash table support. Again, in DrScheme, we can use make-hash-table

(define tbl (make-hash-table))
(hash-table-put! 'foo 'bar)
(hash-table-get 'foo)             => bar
(hash-table-get 'boo)             => ; error!!

dugan@cs.washington.edu (Last Update: )