It has been said that the universe is made of cons cells. Believe it or not, lists in Scheme are made of the same substance. Coincidence? You be the judge.
A cons cell, or a pair, is an object that references two other objects. The two references in a cons cell are called the car and the cdr. cons is a useful function that creates a cons cell with the given car (first) and cdr (second):
> (cons 1 2)
(1 . 2)
> (cons 'left 'right)
(left . right)
You can build elaborate data structures by connecting cons cells together. For example, by making the cdr of a cons cell point to another cons cell, we can start chaining conses together to make a linked list:
> (cons 'a (cons 'b 'end))
(a b . end)
You'll notice that this doesn't look quite like the lists we've
used to make expressions like
(+ 1 2 3)--it has that funny dot in it.
The reason is that this is not a proper list; it is an improper list or
dotted list. The issue here is definitional; there is a specific
definition for what constitutes an actual list in Scheme, and here it is:
A list is either the empty list, or a pair whose cdr is a list.
Notice again that this definition is recursive. Also, in order to define lists, we had to introduce a new kind of object: the empty list. The empty list is written as () and is defined to be the list with no elements. The reason for such fussiness in defining lists will become clear once we start writing algorithms that operate on them. Anyway, now we know how to build proper lists:
> (cons 'a (cons 'b '()))
(a b)
In practice, doing something like this is silly since the Scheme reader knows how to build this cons cell structure for us from a typed-in list representation:
> '(a b)
(a b)
As an exercise, consider this: What structure did the reader create when we typed the expression that explicitly creates two cons cells to form (a b)?
Note that the empty list is emphatically not a cons cell. Scheme has predicates to help you sort out what is what:
> (list? '())
#t
> (pair? '())
#f
> (pair? '(a b))
#t
> (null? '())
#t
> (null? '(a b))
#f
Discussion questions:
(define (my-list? lst)
When dealing with cons cell structures, it is helpful to draw them out with boxes and arrows. Try drawing the structure of the nested list (a (b c) ((d))) (which we will call lst):
Now work out the values of these expressions (note that if you find yourself using functions like caaddr too often, you probably need more abstraction).
>(car lst)
>(cdr lst)
>(cadr lst)
>(cadadr lst)
>(caaddr lst)
> (list 1 2 3 ...)
(1 2 3 ...)
list builds a list of its arguments.
> (append '(a b) '(c d) ...)
(a b c d ...)
Think of append as sewing its argument lists together.
> (map square (list 1 2 3 4 5))
(1 4 9 16 25)
quote is a special form that simply returns its argument unevaluated. It can be abbreviated as a prefix single quote (').
> (quote (apple peach pear))
(apple peach pear)
Try to figure out what this function does. You may want to consider the following:
(define (enigma baz qux)
(cond ((null? qux) 0)
((equal? baz (car qux)) (+ 1 (enigma baz (cdr qux))))
((pair? (car qux)) (+ (enigma baz (car qux))
(enigma baz (cdr qux))))
(else (enigma baz (cdr qux)))))
A filter is a device that lets some inputs through while blocking others. We can imagine applying this idea to Scheme lists. Let's say we have a list of integers representing the addresses of internet users who have visited our website. We would like to process this list to extract statistics like the number of unique users, the number of users from a particular network (such as Harvard's campus network), and so on.
Filtering functions are quite useful for this task. One thing we must do first is remove addresses that don't count for various reasons. For example, we know that we obsessively visit our own site every day, so we should remove our address from the list to get more realistic data.
Write a function that can remove all occurrences of a particular number from a list of numbers (don't worry too much about error checking):
(define (remove-eq-to-n lst n)
Next, we want to count unique users. We can do that by removing duplicate entries from the list. The function we just wrote should be helpful.
(define (remove-duplicates lst)
Good software engineers should always be on the lookout for code that can be made re-usable. The function remove-eq-to-n would be a lot more useful if it could work on lists of anything. Write a more general filter function that takes a predicate (function) as an argument, and removes all items that fail to satisfy the predicate:
(define (filter lst pred)
Soon you will see how easy it is to implement a function like remove-eq-to-n in terms of filter.
This one's a little tricky. Try applying the following strategy:
(define (mystery foo bar)
(cond ((and (null? foo) (null? bar)) '())
((null? foo) (append bar foo))
((null? bar) (cons (car foo)
(mystery bar (cdr foo))))
(else (cons (car foo)
(cons (car bar)
(mystery (cdr foo)
(cdr bar)))))))
Our dictionary's interface is a little different from what you might expect or be used to. We modify a dictionary by creating a new dictionary that's slightly different from an existing one.
We're already used to building up lists in this way, but the algorithms for dealing with trees represented as lists are not immediately clear. Let's look at an example. What tree structure would you expect to result from the following expression? Try drawing a cons cell diagram.
(dicttree-extend (dicttree-extend (dicttree-extend (dicttree-new)
'orange
"C")
'carrot
"A")
'spinach
"E")
Examine our implementation of dicttree-lookup. How is dicttree-keys different? We're asking for a list of the keys in the dictionary, so this should strike you simply as a list building function like the several others we've seen already.
Starting now, we will be watching your coding style like hawks, and so should you. Prudent and consistent style is a big help when you read over code, debug it or try to remember how it works.
A few important points to remember:
(if (= (+ (square a) (square b)) (square c)) #t #f)
becomes simply:
(= (+ (square a) (square b)) (square c))
Think functionally. Every expression already yields a value, so there is rarely
a need to explicitly return one object or another.
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -no_navigation -split 0 sec2.tex
The translation was initiated by CS51 Course Library on 2008-02-10