# Scheme Programming/List Operations

Lists are a fundamental data structure in Scheme, as they are in many other functional languages. While among the simplest of structures, they have a rich set of operations and an amazing variety of uses. In this section, we'll cover the basics of creating and using lists.

## Scheme Lists[edit | edit source]

A list is a sequence of elements ending with `()`

, sometimes called
the "empty list" or "nil". We can build up lists with `cons`

, which
attaches a new element to the head of a list:

```
> '() ; The empty list must be quoted.
()
> (cons 3 '())
(3)
> (cons 2 (cons 3 '()))
(2 3)
> (cons #t (cons 2 (cons 3 '())))
(#t 2 3)
```

The first argument of `cons`

may be any Scheme object, and
the second is a list; the value of `(cons x xs)`

is a new list which
contains `x`

followed by the elements of `xs`

.^{[1]} (Scheme's way of
printing lists uses a shorthand which hides the final `()`

. In
the responses above, we simply see the elements of a list enclosed in
parentheses.) It's important to note that we must always quote `()`

,
in order to prevent Scheme from trying to interpret it as an (invalid)
expression.

Two predicates define the Scheme list type. `null?`

,
is true for `()`

(the empty list) and is false otherwise, while
`pair?`

returns true only for objects constructed with
`cons`

.^{[2]}

There are two basic functions for accessing the elements of lists. The first,
`car`

,
extracts the first element of a list:

```
> (car (cons 1 '()))
1
> (car (cons 2 (cons 3 '())))
2
> (car '())
; Error!
```

Applying `car`

to the empty list causes an error.

The second function, `cdr`

, gives us the tail of a list: that is, the
list without its leading element:

```
> (cdr (cons 1 '()))
()
> (cdr (cons 2 (cons 3 '())))
(3)
> (cdr '())
; Error!
```

As with `car`

, trying to apply `cdr`

to the empty list causes an error.

The three functions `cons`

, `car`

, and `cdr`

satisfy some useful
identities. For any Scheme object *x* and list *xs*, we have

```
(car (cons x xs)) = x
(cdr (cons x xs)) = xs
```

For any non-empty list *ys*, we also have

```
(cons (car ys) (cdr ys)) = ys
```

Clearly, building a list through successive `cons`

operations
is clumsy. Scheme provides the built-in function `list`

which
returns a list of its arguments:

```
> (list 1 2 3 4)
(1 2 3 4)
> (cons 1 (cons 2 (cons 3 (cons 4 '())))) ; equivalent, but tedious
(1 2 3 4)
```

`list`

can take any number of arguments.

We can write a range of useful functions using just `cons`

, `car`

,
and `cdr`

. For example, we can define a function to compute the length of
a list:

```
(define (length xs)
(if (null? xs)
0
(+ 1 (length (cdr xs)))))
```

This definition, like the definitions of most list operations, closely follows
the recursive structure of a list. There is a case for the empty
list (which is assigned the length 0), and a case for a non-empty list (the length
of the tail of the list, plus one). In practice, Scheme provides
`length`

as a built-in function.

Here's another simple example:

```
(define (find-number n xs)
(if (null? xs)
#f
(if (= n (car xs))
#t
(find-number n (cdr xs)))))
```

`find-number`

returns `#t`

if the argument *n* occurs in the list
*xs*, and returns `#f`

otherwise. Once again, this definition follows
the structure of the list argument. The empty list has no elements,
so `(find-number n '())`

is always false. If `xs`

is non-empty, then
*n* could be the first element, or it could be somewhere in the tail.
In the former case, `find-number`

returns true immediately. In the
latter, the return value should be true if *n* appears in `(cdr xs)`

and false otherwise. But since this is the definition of `find-number`

itself, we have a recursive call with the new argument `(cdr xs)`

.

## Notes[edit | edit source]

- ↑ This
is a simplified account which is correct for our current purposes. In fact,
`cons`

constructs*pairs*of its arguments, both of which may be arbitrary Scheme objects. A pair whose second element is`()`

or another pair is called a list; all other pairs are called*improper*. - ↑ The definition of the Scheme list type is
looser than that of numbers, booleans, etc.
While the (scheme list) library provides a true
`list?`

function, this function is defined in terms of`null?`

and`pair?`

. See the previous note.