Lists are much more versatile than arrays. With lists, you can recurse (e.g., for mapping or folding) by cdring down a list. This doesn't work for arrays; you'd have to pass in the array index too.
For example, this is a simple implementation of map
and fold
that take one list only:
(define (map1 f l)
(if (null? l) l
(cons (f (car l)) (map1 f (cdr l)))))
(define (left-fold1 f init l)
(if (null? l) init
(left-fold1 f (f (car l) init) (cdr l))))
How would you do that for arrays, without having to pass in another argument (for the index)? (Remember, Lisp and Scheme have no pointers, at least none that user code can touch.)
Also, lists can share storage, but arrays cannot. Take this Scheme code for example:
(define (x-world x)
(cons x '(world)))
(define hello-world (x-world 'hello))
(define goodbye-world (x-world 'goodbye))
Here, hello-world
has the value (hello world)
and goodbye-world
has the value (goodbye world)
.
There is one important fact, though: in many Scheme implementations, the (world)
part of both lists is actually shared. This sharing would be impossible for arrays.
Addendum: To answer compman's point that recursion is somehow "non-production-grade", in Scheme, all standard looping/iteration is done using tail recursion. Here's a tail-recursive version of map1
, for example:
(define (map1 f l)
(let loop ((r '())
(l (reverse l)))
(if (null? l) r
(loop (cons (f (car l)) r) (cdr l)))))
or, even more simply using left-fold1
:
(define (map1 f l)
(left-fold1 (lambda (e r) (cons (f e) r))
'() (reverse l)))
reverse
is a Scheme built-in, but its implementation is equally trivial (and also uses iteration only):
(define (reverse l)
(left-fold1 cons '() l))
Single dispatch is somewhat easier to implement, and multiple dispatch is rather rarely needed in practice according to research by Muschevici et al.
You can find more information in the Wikipedia article on multiple dispatch; for instance, it also explains why the CLOS method of defining multimethods may be a better fit for Lisp's extremely uniform syntax, rather than for the more prevalent nesting of methods within classes.
Best Answer
A Lisp list is not really terminated with an empty list -- it's terminated with a special value, traditionally called
nil
. As it happens, that also traditionally evaluates asfalse
-- which makes it about as close to C's null pointer as you can get (in C, a null pointer constant is an integer constant equal to zero, which also evaluates tofalse
).An empty list is basically just a rather short-hand way of expressing NIL -- since you don't even have a single cons cell, all you're left with is the NIL that terminates the list. In other words, it's not that a list is terminated with an empty list -- it's that an empty list consists of only a terminator.
Using dot notation, it's possible to link cons cells together in other ways, but the result isn't a "list" as the term is normally used.