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 cdr
s. The car
s 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:
-
Write
length
, which is likecount
but for lists.(define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst))) ))
-
Write
append
, taking in two lists as arguments. (The realappend
can take any number of arguments, but let's put that aside for now.)(define (append left right) (if (null? left) right (cons (car left) (append (cdr left) right)) ))
This is a very familiar form. In fact, if we just replaced
cons
with+
andright
(in the base case) with0
, we'd have a method that summed up the numbers inleft
.In general, when we see a pattern like this, we figure it might be useful to have a more general function that we could just plug things into. In this case, that function is
accumulate
, which is the last of the three major higher-order procedures (along withmap
andfilter
).(define (accumulate combiner base-case lst) (if (null? lst) base-case (combiner (car lst) (accumulate combiner base-case (cdr left))) ))
Now, we can write
append
as follows:(define (append left right) (accumulate cons right left) )
But this only works for the two-argument version of
append
. Again, the realappend
can take any number of arguments. -
Write
list?
, which returns true if and only if its argument is a valid list. You'll probably want to usepair?
andnull?
(the list version ofempty?
) in your answer!(define (list? x) (cond ((pair? x) (list? (cdr x))) ((null? x) #t) (else #f) ))
Notice how the logic here matches the definition of a list from above! Whenever your code matches your algorithm this closely, it's a good thing. It's easier to understand and you're less likely to make mistakes.
If we wanted to really mirror the original definition, we could write it like this:
(define (list? x) (or (and (pair? x) (list? (cdr x))) (null? x) ))
But this sacrifices a bit of readability. Personally I think the first one's a good balance!
-
If
(list? mystery)
is#t
, but(pair? mystery)
is#f
, what ismystery
?There's only one thing that's a list but not a pair; we could almost think of it as a list that has no pairs. That's the empty list,
()
.
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.
-
(a . b)
+---+---+ -->| o | o | +-|-+-|-+ v v a b
-
(a)
+---+---+ -->| o | / | +-|-+---+ v a
Remember, we represent the empty list
()
as a slash through the box. -
(a b c)
+---+---+ +---+---+ +---+---+ -->| o | o---->| o | o---->| o | / | +-|-+---+ +-|-+---+ +-|-+---+ v v v a b c
-
(a b . c)
+---+---+ +---+---+ -->| o | o---->| o | o | +-|-+---+ +-|-+-|-+ v v v a b c
How do you do this kind of problem, that deals with these "improper lists"? (They aren't lists at all—your
list?
procedure should return#f
for an input like this.) The easiest way is probably to just pretend the lastcdr
is an empty list, and write out the list spine as usual. Then you can go back and set the lastcdr
to whatever it really is. -
((a . b) . c)
+---+---+ -->| o | o----> c +-|-+---+ v +---+---+ | o | o | +-|-+-|-+ v v a b
-
((a) b (c))
+---+---+ +---+---+ +---+---+ -->| o | o---->| o | o---->| o | / | +-|-+---+ +-|-+---+ +-|-+---+ v v v +---+---+ b +---+---+ | o | / | | o | / | +-|-+---+ +-|-+---+ v v a c
Now let's try going the other way. There's a very simple two-step process to this:
- Write every pair as
(car . cdr)
. - 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:
((a . ()) . (b . ((c . ()) . ())))
((a . ()) . (b . ((c . ()) . ())))
((a) b (c))
Let's practice!
-
+---+---+ +---+---+ +---+---+ -->| o | o---->| o | o---->| o | / | +-|-+---+ +-|-+---+ +-|-+---+ v v v a b c
(a b c)
-
+---+---+ --->| o | o | +-/-+-\-+ / \ / \ / \ v v +---+---+ +---+---+ | o | o | | o | o | +-|-+-|-+ +-|-+-|-+ v v v v a b c d
((a . b) c . d)
If you don't get this one, try working it out following the steps very carefully!
-
+---+---+ +---+---+ --->| o | o---->| o | o | +-|-+---+ +-/-+-|-+ v / v a / c / v +---+---+ | o | / | +-|-+---+ v b
(a (b) . c)
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)) )))
-
First off, this code has a bug in it! Where is it?
When we ask for
caar
ofassign-list
, that gives us thecar
of the first element of the list—that is, thecar
of an assignment. But thecar
of an assignment is the name, not the number of points!Without fixing anything further, this would have to be
cdar
instead ofcaar
to even return a correct answer. -
The code could be improved to actually use the data abstraction set up at the top. What needs to change?
Instead of asking for
(caar assign-list)
or the "correct"(cdar assign-list)
, we should instead say(assign-points (car assign-list))
."But this is more typing!" some of you say. Well, it is, but it does something important. If, for example, we changed the representation of assignments so that the
car
had the points instead of thecdr
, we wouldn't have to hunt down all thecdr
s in our program and change them.In addition, we're saying something important here. "I want the point value of this assignment" makes sense. "I want the cdr of this assignment"...really doesn't. Assignments don't have
cdr
s. Neither do people, web pages, or spaceships. By using the second form, we're stating what we mean, rather than what the computer might have to do to carry out what we mean. It's also easier to read.Finally, the original author of the code would have never mixed up
caar
andcdar
if he had just been using the right abstract selectors to begin with."But wait. There's still a
car
in there...and acdr
too! Doesn't data abstraction mean we shouldn't use those?" Well, no, data abstraction just says you should use the constructors and selectors appropriate for your data. In this caseassign-list
is a list of assignments. Since it's a list,car
andcdr
are appropriate. -
Write
count-of
, which counts how many times a certain item appears in a list.(define (count-of item lst) ; Implementation here )
(define (count-of item lst) (cond ((null? lst) 0) ((equal? item (car lst)) (+ 1 (count-of item (cdr lst))) ) (else (count-of-item (cdr lst))) ))
-
Write
deep-count-of
, which is likecount-of
but also checks sublists.(define (deep-count-of item lst) ; Implementation here )
There are two ways to write this one. The first is a modification of our answer for
count-of
:(define (deep-count-of item lst) (cond ((null? lst) 0) ((list? (car lst)) (+ (deep-count-of item (car lst)) (deep-count-of item (cdr lst)) )) ((equal? item (car lst)) (+ 1 (deep-count-of item (cdr lst))) ) (else (deep-count-of-item (cdr lst))) ))
The second is to forget that we're working with lists at all, and just say "always check the cars and cdrs of pairs". In this case the argument that was
lst
is now "the thing we're looking at", whether it's a list or a word.(define (deep-count-of item current) (cond ((equal? item current) 1) ((pair? current) (+ (deep-count-of item (car current)) (deep-count-of item (cdr current)) )) (else 0) ))
-
(Harder!) Write
interleave
, which takes two lists and returns a new list with alternating elements. The two lists might not be the same length!> (interleave '(1 2 3) '(a b c d) (1 a 2 b 3 c d) > (interleave '(1 2 3) '(a)) (1 a 2 3) (define (interleave left right)
This is tricky, but the easiest way to do it turns out to be to only handle one element at a time. We know that when we start, the first element in the result in going to be the
car
of the left list. If the left list is already empty, we can just throw in everything in the right list, just likeappend
. (This is true even if the right list is also empty.)That leaves one tricky bit: what happens after the first element? Well, we do the same thing, but switch "right" and "left" everywhere in the above paragraph. Repeat until one of the lists runs out.
We can actually write a solution like that, and it would look like this:
(define (interleave left right) (if (null? left) right (cons (car left) (interleave-right (cdr left) right) ))) (define (interleave-right left right) (if (null? right) left (cons (car right) (interleave left (cdr right)) )))
But we can do better. Instead of switching the words "right" and "left", how about just switching the arguments themselves in the recursive call? That'll work!
(define (interleave left right) (if (null? left) right (cons (car left) (interleave right (cdr left)) )))
Think of this as "braiding" the two lists together; they criss-cross back and forth until one or the other runs out.
Harder List Questions
Back to Jordy's home page | Course home page