Building Hierarchy

Composing pairs and lists

Previously we saw how to use cons to "group" a pair of values together, e.g. (cons 1 2), which returns a pair (1 . 2). We can also use list to group an arbitary amount of data together. For example if you type (list 1 2 'bagel 4) in the interpreter, Racket will print the list (1 2 bagel 4). Notice that we can put any sort of data inside them, even other pairs and lists!

Now let's make a pair of lists:

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

The first item of the pair is the list (1 2) and the second is the list (3 4). We can show this structure with the following box-and-pointer diagram:

(If you aren't familiar with drawing and interpreting box-and-pointer diagrams, please go back and review the section in Lesson 4.)

You can also represent the structure ((1 2) 3 4) using a little-t tree:

With litle-t trees, every element in a sequence is a node. In the example above, (1 2) is an element of ((1 2) 3 4), so it's a node. But it's also a tree with two children nodes—one for each element.

Why do we call this a "little-t tree"? Later on in this lesson, we'll discuss the "capital-T Tree" data type, which is completely different from the little-t tree data type. We use this notation for the sake of consistency and clarity.

We may also refer to little-t trees as deep lists (since they are lists within lists within lists within...), which is less ambiguous, but also less descriptive of the tree-like structure of lists of lists.

Takeaways

In this section, we discussed nested cons structures. We also introduced little-t trees.

Before We Continue...

Review the shorthand notation for cars and cdrs. It will come in handy!