### Lists Again

Suppose we want to make a list of symbols whose print names are the English words for the first five integers. We could do it using quoting, of course, like this:

```Scheme>(define firstfive '(one two three four five))
#void
Scheme>firstfive
(one two three four five)
```

We don't have to quote each symbol individually. Within a `quote` expression, everything is assumed to be literal data, not expressions to evaluate.

We could also do it by calling `list` to construct the list, and handing it each of the five symbols as literals. To do that, we have to quote them, so that Scheme won't think we're referring to variables named `one`, `two`, etc.

```Scheme>(define firstfive (list 'one 'two 'three 'four 'five))
#void
Scheme>firstfive
(one two three four five)
```

Since `list` is a procedure, its argument expressions are evaluated. We use a `quote` around each expression, so that it will return a pointer to the appropriate symbol, rather than the value of the variable by the same name.

This works whether or not there is a variable by that name, because names of symbols and names of variables are completely different things.

For example, even after evaluating the above expressions, attempting to evaluate the expression `four` will be an error, unless we've defined a variable named `four`. The existence of a symbol with a given print name doesn't say anything about the existence of a variable with that name.

#### Heterogeneous Lists

Since Scheme is dynamically typed, we can put any kind of object in a list. So far, we've made a list of integers and a list of symbols. We can also make a list of different kinds of things, such as a list of integers, symbols, and lists.

```Scheme>(define mixed5 '(one 2 (three and a) "four" 5))
#void
Scheme>mixed5
(one 2 (three and a) "four" 5)
```

Here we've constructed a mixed list whose first element is a symbol, the second is an integer, the third is a list of symbols, the fourth is a string, and the fifth is another integer. (The technical term for a mixed list is a "heterogeneous list.")

We can draw it like this:

```       +-----+
mixed5 |  +--+-->+---+---+  +---+---+  +---+---+  +---+---+  +---+---+
+-----+   | + | +-+->| + | +-+->| + | +-+->| + | +-+->| + | * |
+-+-+---+  +-+-+---+  +-+-+---+  +-+-+---+  +-+-+---+
|          |          |          |          |
\|/        \|/         |         \|/        \|/
one         2          |        "four"       5
|
\|/
+---+---+  +---+---+  +---+---+
| + | +-+->| + | +-+->| + | * |
+-+-+---+  +-+-+---+  +-+-+---+
|          |          |
\|/        \|/        \|/
three       and         a

```

Notice that we draw the symbols (`one`, `three`, `and`, and `a`) as simple sequences of characters. This is just a drawing convention. They're really objects, like pairs are. We draw strings similarly, but with double quotes around them. Don't be fooled--these are objects on the heap, too. We just draw them this way to keep the picture from getting cluttered up.

#### Operations on Lists

We've already seen two list-processing procedures that you'll use a lot, `car` and `cdr`. `car` takes a pointer to a pair, and extracts the value of its first (`car`) field. `cdr` takes a pointer to a pair and returns the value of its second (`cdr`) field.

(It might have been better if `car` had been called `first` and `cdr` had been called `rest`, since that's more suggestive of how they're used: a pointer to the first item in a list, and a pointer to the pair that heads the rest of the list.)

Given our list stored in `mixed5`, we can extract parts of the list using `car` and `cdr`.

```Scheme>(car mixed5)
one
Scheme>(cdr mixed5)
(2 (three and a) "four" five)
```

By using `car` and `cdr` multiple times, we can extract things beyond the first element. For example, taking the `cdr` of the `cdr` of a list skips the first two elements, and returns the rest:

```Scheme>(cdr (cdr mixed5))
((three and a) "four" 5)
```

Taking the car of that list (that is, the `car` of the `cdr` of the `cdr`) returns the first item in that list:

```Scheme>(car (cdr (cdr mixed5)))
(three and a)
```

We can keep doing this, for example taking the second element of that sublist by taking the car of its cdr.

```Scheme>(car (cdr (car (cdr (cdr mixed5)))))
and
```

This starts to get tedious and confusing--too many nestings of procedures that do too little at each step--so Scheme provides a handful of procedures that do two list operations at a whack. The two most important ones are `cadr` and `cddr`.

`cadr` takes the `car` of the `cdr`, which gives you the second item in the list. `cddr` takes the `cdr` of the `cdr`, skipping the first two pairs in a list and returning the rest of the list.

This lets us do the same thing we did above, a little more concisely and readably:

```Scheme>(cadr (car (cddr mixed5)))
and
```

With a little practice, it's not hard to read a few nested expressions like this. In this example, taking the `cddr` of `mixed5` skips down the list two places, giving us the list that starts with the sublist we want. Then taking the `car` of that gives us the sublist itself off the front of that list, and taking the `cadr` of that gives us the second item in the sublist.

Of course, even if Scheme didn't provide `cadr` and `cdr`, you could write them yourself in terms of `car` and `cdr`:

```(define (cadr x)
(car (cdr x)))

(define (cddr x)
(cdr (cdr x)))
```

Scheme actually provides predefined list operations for all combinations of up to four `car`'s and `cdr`'s. For example, `cadadr` takes the `cadr` of the `cadr`. (The naming scheme is that the pattern of `a`'s and `d`'s reflects the equivalent nesting of calls to `car` and `cdr`.)

You probably won't want to bother with most of those, because the names aren't very intuitive. Two procedures that are worth knowing are `list-ref` and `list-tail`.

`(list-ref` list n`)` extracts the nth element of a list `list`, which is equivalent to n-1 applications of `cdr` followed by `car`. For example, `(list-ref '(a b c d e) 3)` is equivalent to `(car (cdr (cdr '(a b c d e))))`, and returns `d`.)

In effect, you can index into a list as though it were an array, using `list-ref`. (Of course, the access time for an element of a list is linear in the index of the element. If you need constant-time access, you can use vectors, i.e., one-dimensional arrays.) Notice that the numbering is zero-based, which is why `(list-ref lis 3)` returns the fourth element of a `lis`. This is consistent with the indexing of vectors, which are also zero-based, as well as reflecting the number of `cdr` operations.

`(list-tail` list n`)` skips the first n elements of a list and returns a pointer to the rest, which is equivalent to repeated applications of `cdr`. (This is standard R4RS Scheme, but not IEEE Scheme. If your Scheme doesn't provide `list-tail`, you can easily write your own.)

These two procedures can make it much clearer what you're doing when you extract elements from nested lists. Suppose that we have a list `foo`, which is a triply-nested list--a list of lists of lists, and we want to extract the second element of the bottom-level list that is the third element of the middle-level list that is the fourth element of the outermost list.

We could write `(car (cdr (car (cdr (cdr (car (cdr (cdr (cdr foo)))))))))`, but that's pretty hard to read. If we use `cadr`, `caddr`, and `cadddr`, we can make it somewhat more readable by using one function call at each level of structure: `(cadr (caddr (cadddr foo)))`. But it's still clearer to write `(list-ref (list-ref (list-ref foo 4) 3) 2)`

or (indented)

```(list-ref (list-ref (list-ref foo 4)
3)
2)
```

`list-ref` and `list-tail` are much more convenient than things like `caddr` when the indexes into a list vary at run time. For example, we might use an index variable `i` (or some other expression that returns an integer) to pick out the ith member of a list: `(list-ref foo i)`. Writing this with `car` and `cdr` would require writing a loop or recursion to perform n-1 `cdr`'s and a `car`.

```==================================================================
This is the end of Hunk N

At this point, you should go back to the previous chapter and
read Hunk O before returning here and continuing this tutorial.
==================================================================
```

(Go BACK to read Hunk O, which starts at section Tail Recursion (Hunk O).)