4

I do not see why we need nil [1] when to cons a sequence (so-called proper list) of items. It seems to me we can achieve the same goal by using the so-called improper list (cons-ed pairs without an ending nil) alone. Since Lisps [2] have already provided a primitive procedure to distinguish between a pair? and an atom (some implementations even provide atom?), when defining a procedure on a list, e.g., length, I can do the same with just dotted-pairs, as shown below:

(define len
  (lambda (l)
    (cond ((pair? l) (+ 1 (len (cdr l))))
          (else 1) ) ) )

It is obvious that we can apply this procedure to an improper list like '(1 . (2 . 3)) to get the expected answer 3, in contrast to the traditional (length '(1 2 3)).

I'd like to hear any opinions in defense of the necessity of nil. Thanks in advance.

[1] Let's ignore the debate among nil/NIL, '() and ().

[2] Here it means the Lisp family of languages.

day
  • 2,292
  • 1
  • 20
  • 23
  • 5
    think of what would happen if you had a list of lists? and you'll see why `nil` is needed. – Dan D. Jan 30 '12 at 10:24

2 Answers2

20

Working with lists without nil (or '()) would be like doing arithmetic without zero. Using only pairs without nil, how would we represent an empty list, or a singleton list '(1)?

It gets worse: since lists don't have to be lists of atoms, but can contain other lists, how would we represent the nested list '(1 2 (3 4))? If we do the following conversions:

'(3 4) => '(3 . 4)
'(1 2 x) => '(1 . (2 . x)) == '(1 2 . x)

we get:

'(1 2 (3 4)) => '(1 . (2 . (3 . 4))) == '(1 2 3 . 4)

But also:

'(1 2 3 4) => '(1 . (2 . (3 . 4))) == '(1 2 3 . 4)

So constructing lists only using pairs and no nil prevents us from distinguishing between a nested list structure and a flat list, at least at the end of the list. You can still include nested lists as any element except the last, so now there's a strange and arbitrary limitation on what the elements of a list can be.

More theoretically, proper lists are an inductively defined data type: a list is either the empty list, or it has a first element, which can be anything, and a rest, which is always another list defined in the same way. Take away the empty list, and now you have a data type where the rest might be another list, or it might be the last element of the list. We can't tell except by passing it to pair?, which leads to the problem with nested listing above. Keeping nil around lets us have whatever we like as list elements, and allows us to distinguish between 1, '(1), '((1)) and so on.

  • Jon, thanks for your answer. Could you give a scenario where singleton would be useful? Thanks. – day Jan 30 '12 at 14:00
  • 1
    I think it comes down to having a consistent interface. If you have a function that might return no items, one item, or many items, it's annoying (at the very least) to have to add special code for the one-item case. One example is parsing a string with an ambiguous grammar: the parser might fail, returning `'()`, or match once, or any number of times. Also, a nice part of Lisp is functions like `map` and `filter` that work on a list of `` without having to know its internal details. These would be harder to write without the inductive definition of a proper list. –  Jan 30 '12 at 16:37
  • 1
    To clarify a bit more: Suppose we changed the parsing/matching function so that in the one-match case it simply returns the plain result, instead of a singleton list. Now every user of the function has to do an extra `pair?` check on the return value before doing anything else with it. (And that might not even work: what if the results of your parser are themselves lists?) For almost all purposes, there's nothing inherently special about a one-item list, so this is extra code and effort that adds nothing. –  Jan 30 '12 at 16:49
  • No problem! Hope it was helpful. –  Jan 30 '12 at 19:50
1

You need it to represent "Nothing".

grettke
  • 1,407
  • 7
  • 10