Pairs and Lists

A pair is the basic data type of Scheme, but what you'll usually be working with are lists. A list is basically a bunch of pairs chained together by their cdrs. The cars are all the elements of a list, and at the end of the chain is the empty list, (). That's actually the definition of a list:

A list is either a pair whose cdr is a list, or the empty list.

Unlike a real data abstraction, Scheme actually understands lists just as much as pairs. That means that when you have a pair whose cdr is another pair:

   +---+---+   +---+---+
-->| o | o---->| o | / |
   +-|-+---+   +-|-+---+
     v           v
     a           b      

Scheme will print it as (a b). (Notice how we represent the empty list as a slash through the last box.)

By the way, when drawing a box-and-pointer diagram, always include the start arrow!

Here's some simple practice with lists:

Box-and-Pointer Diagrams

We use these diagrams to draw structures made out of pairs, including lists. You should be able to draw and understand these for the midterm and the rest of the course!

First, try turning these pair structures into box-and-pointer diagrams. Remember to start out by figuring out how many pairs are in the spine of the list (or improper list), then fill in the elements.

Now let's try going the other way. There's a very simple two-step process to this:

  1. Write every pair as (car . cdr).
  2. Cross out every dot next to an open paren: ". (". Then cross out the open paren as well, plus its matching close paren.

And if we try it on the solution to the last problem above:

  1. ((a . ()) . (b . ((c . ()) . ())))
  2. ((a . ()) . (b . ((c . ()) . ())))
  3. ((a) b (c))

Let's practice!

Data Abstraction

Pairs and lists are great, but a real problem usually deals with people, or web pages, or spaceships. That's why we use data abstraction to think in terms of our abstract data type, rather than the "concrete" types inside Scheme (pairs, functions, etc).

Here's a case where we have an abstract "assignment" type, but the person writing the code to use it clearly didn't get the point.

(define (make-assign name points)
  (cons name points))
(define assign-name car)
(define assign-points cdr)

; Totals up the number of points for
; a list of assignments.
(define (total assign-list)
  (if (null? assign-list)
      0
      (+ (caar assign-list)
         (total (cdr assign-list)) )))