# Scheme Programming/List Operations

 Scheme Programming ← Further Maths List Operations Vector 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

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`. (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`.

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)`.