6.001/Recitation 5

Rob Speer

Contents 1 Building blocks of data structures 2 Bob the Angry Flower introduces the empty list 3 The list convention 3.1 Printed representations 3.2 Improper lists 3.3 Trees 4 List procedures 5 Brain teaser 6 Problems 7 A data abstraction

Building blocks of data structures

You only need one thing to build all kinds of data structures: the pair.

• The procedure cons creates a pair.
• car returns the first element of a pair.
• cdr returns the second element of a pair.

It would also be nice if we had a conventional "base case" for data structures. That's the empty list, which is spelled ().

Bob the Angry Flower introduces the empty list

Some confusion about the empty list may creep into this class - sometimes even from people on the course staff. The empty list is strange in MIT Scheme, and slightly stranger in 6.001 Scheme. Let's clear things up now in a particularly hostile way, by pointing out things that may have once been true about the empty list, but no longer are the case in DrScheme.

Three things that are wrong about the empty list "The empty list is a false value" (No! There is no false but #f itself.) "The empty list is actually just another name for #f" (That was a great way to get confusing printouts. DrScheme keeps them separate.) "You can use the predefined name nil to mean #f or the empty list" (Define it if you want to. It doesn't save any typing, though.)

So don't think these are true. Don't count on them being false, either. Really, just don't ever use the empty list as a truth value, and Bob will be happy.

The list convention

Oh right. So how do we make a non-empty list? By following this convention:

1. Every non-empty list is a pair.
2. The car of this pair is the first item in the list.
3. The cdr of this pair is another list, containing everything but the first item.

Hey, those are singly-linked lists. We can draw them with box-and-pointer diagrams.

Printed representations

• A pair looks like this: (1 . 2)
• But a list looks like this: (1 2 3)
• Even though it could also be thought of as this: (1 . (2 . (3 . ())))

Improper lists

Every once in a while you'll encounter a data representation that uses improper lists. These lists break rule 3: if you keep taking the cdr, you find something that's not a list at the end. These are printed like this: (1 2 3 4 . 5)

Trees

Trees are just lists where some of their items (things that are in a car somewhere) can be lists too.

List procedures

(list arg1 arg2 arg3...)

Takes any number of arguments, and returns its arguments as a list.

(append list1 list2 list3...)

Concatenates lists. Think of it as erasing the parentheses between them.

(list-ref lst n)

Returns the nth item in a list.

(car lst)

Returns the first item in a list. This really is the Right Way, not just a way to ruthless advantage of its pair nature.

(cadr lst)

Returns the second item in a list. It's the car of the cdr. You can extrapolate more function names.

Brain teaser

Make a circular list - one where you can take the cdr forever because it's self-referential, but takes up a finite amount of memory. Using a messy side-effect function like set-cdr! here would be cheating.

Warning: I got this problem from Austin, and I don't know the answer.

Problems

• Draw box-and-pointer diagrams for these structures, and also write their printed representation.

(cons 1 2)



(cons 1 (cons 3 (cons 5 ())))



(cons (cons (cons 3 2) (cons 1 0)) ())



(cons 0 (list 1 2))



(list (cons 1 2) (list 4 5) 3)



(define a (list 1 2))
(list a a)

• Write expressions that print out like the following, and draw their box-and-pointer diagrams.

(1 (2 3))





(1 2 . 3)





(((0)))

• Write a function, reverse, that reverses the order of the elements in a list. (Be sure to return a proper list!)

A data abstraction

It's pretty clear to see how a list can be used as a stack (first in, first out data storage). How about implementing a queue (first in, last out)?

Here's how a queue should behave:

(head (enqueue 5 (empty-queue)))
;Value: 5

(define q (enqueue 4 (enqueue 5 (enqueue 6 (empty-queue)))))

(head q)
;Value: 6

(head (dequeue q))
;Value: 5

Write empty-queue, enqueue, dequeue, and head so that these work appropriately. This should not be a hard problem, but it lets us talk about abstractions.