Why do you have to cons with a null to get a proper list in scheme?

Question

I realize this is a total n00b question, but I'm curious and I thought I might get a better explanation here than anywhere else. Here's a list (I'm using Dr. Scheme)

> (list 1 2 3)
(1 2 3)

Which I think is just sugar for this:

> (cons 1 (cons 2 (cons 3 null)))
(1 2 3)

This, on the other hand, does something else:

> (cons 1 (cons 2 3))
(1 2 . 3)

My questions is, why is that different? What's the point of requiring the null at the end of the list?

Answer 1

The definition of a list is recursive.

 1. The null list (empty list) is a list
 2. A list is made up of an item cons a list

So these are lists:

1. null  => ()  --read as empty list
2. cons 3 null  =>  (3)
3. cons2 (cons 3 null)  => (2, 3)

The last example you gave cons 2 3 does not conform to this list definition so its not a list. That is cons accepts an item and a list. 3 is not a list.

Answer 2

cons adds a new element to the beginning of a list, so what you're doing when you write:

(cons 1 (cons 2 (cons 3 null)))

is recursively adding items to an ever-growing list, starting with null, which is defined to be the empty-list (). When you call (cons 2 3) you're not starting with the empty list to begin with, so are not constructing a list by appending 2 to its beginning.

Answer 3

A cons statement is used to allocate a pair whose car is obj1 and whose cdr is obj2

(cons obj1 obj2)

Therefore, it is necessary to end a cons statement with a null so that we know we are the end of the list.

> (cons 1 (cons 2 3))
(1 2 . 3)

In that example, the cdr would be a pair <2,3> where 2 is the car and 3 is the cdr. Not the same as:

(list 1 2 3)

Answer 4

Lisps, including Scheme, are dynamically typed, and 'the lisp way' is to have many functions over a single data structure rather than different data structures for different tasks.

So the question "What's the point of requiring the null at the end of the list?" isn't quite the right one to ask.

The cons function does not require you to give a cons object or nil as its second argument. If the second argument is not a cons object or nil, then you get a pair rather than a list, and the runtime doesn't print it using list notation but with a dot.

So if you want to construct something which is shaped like a list, then give cons a list as its second argument. If you want to construct something else, then give cons something else as its second argument.

Pairs are useful if you want a data structure that has exactly two values in it. With a pair, you don't need the nil at the end to mark its length, so it's a bit more efficient. A list of pairs is a simple implementation of a map of key to value; common lisp has functions to support such property lists as part of its standard library.

So the real question is "why can you construct both pairs and lists with the same cons function?", and the answer is "why have two data structures when you only need one?"