Lists, the big idea

A list is a chain of pairs

A Scheme list is a chain: each link holds one value and a pointer to the rest of the chain. (list 1 2 3) builds such a chain, and because the links are made of pairs, a list of three values is really three nested pairs with an empty list on the end.

The empty list, written (list), is the end of every chain, and null? is the test that tells you when you have reached it. That test is the reason walking a list is so easy to write: check for the end, use the first value, then ask the same question about the rest.

Two ends, two functions

car gives the first value of a list and cdr gives everything after it. The names are historical and worth taking at face value: first, and rest. list-ref counts along instead, and length counts the whole chain.

Building is just as small. cons puts one value on the front of an existing list, append joins two lists, and reverse turns one around. Notice that nothing here changes the list you started with — new structure is built, and the old list is left as it was.

Proper lists and dotted pairs

cons accepts any two values, and the result is a pair. A proper list is a chain of pairs that ends in the empty list, which is what list builds and what list? recognises.

The printed dot marks the last pair’s tail when it is not a list. (cons 1 2) prints (1 . 2), while (cons 1 (list 2)) prints (1 2) because the second value is a proper list. Both are pairs; only the second is a list.

That distinction matters because the list functions expect a proper list. length, reverse and map walk until they reach the empty list, so a dotted pair gives them no end to find.

Building without changing

Every list function in this chapter builds a new chain; the list you pass in is untouched. (cons 0 xs) makes a new pair whose tail is the old list, and (append xs ys) copies the links of xs onto ys.

That is why sharing is safe. Two names can point at the same list, and adding to one with cons gives a third list without disturbing either. Only the vector chapter has a value that changes in place.

append copies its first argument but not its last, so it is cheapest when the first list is short. reverse builds a new list too, which is why a loop can build backwards and fix the order once at the end.

Taking a list apart

(define xs (list 1 2 3))
(print xs)
(print (car xs))
(print (cdr xs))
(print (cons 0 xs))
(print (append xs (list 4 5)))
(print (reverse xs))
(print (length xs))
(print (list-ref xs 2))

; The end of the chain.
(print (null? xs))
(print (null? (list)))
(print (pair? xs))

The chain is built from the front

cons is the only constructor a list needs. It takes a value and an existing chain and returns a new chain with the value at the front. (cons 1 (cons 2 (list))) is the same list as (list 1 2), built one link at a time, and the empty list is the anchor that makes the last link a proper list.

Building from the front is cheap because nothing is copied. The new pair points at the old chain, so a list of a thousand values can grow by one without touching the thousand. Building from the back with append copies the whole first list, which is why repeated appends in a loop are slow.

Walking is taking the rest

A walk down a list is a repeated cdr: each step drops the first value and hands the remainder on. car reads the value you are standing on. The pair of them, plus null? to recognise the end, is the whole vocabulary of a list traversal.

Try these next

• Build (list 1 2 3) with three cons calls and no list.
• Print (cdr (cdr (list 1 2 3))) and predict it before running.
• Join two lists with append, then reverse the result and compare with reversing each first.