In Lisp and other functional languages, why is length not O(1)

Question

The list primitives in Lisp have the opperator length defined as follows:

(define (length lst)
  (if (null? lst) 0 (+ 1 (length (cdr lst)))))

Why can't implementers of some Lisp make length a primitive computed in constant time?

Thanks

Answer 1

The reason is the "traditional" implementation of lists in Lisp. Elsewhere, lists are sometimes implemented similarly to an array. So, when you create a list, it's a single, self-contained thing.

An array-like list: [ 1 2 3 4 5 6 ]

If you wanted to tack an item -- '0', for example -- to the beginning of that list (and assuming the list implementation is simplistic), all the items in the list would be shifted up (to the right). Then, the '0' would be installed in the new spot.

Step 0. [ 1 2 3 4 5 6 ]
Step 1. [   1 2 3 4 5 6 ] (Shift Right)
Step 2. [ 0 1 2 3 4 5 6 ] (Insert)

That is not how (traditional) Lisp lists are at all. Every item of the list is a separate piece that points to the next item. The parts of the list are called "conses". (This is called a linked-list.)

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

Huh? Well, each of those items is a cons cell. And each cons cell holds two values: car and cdr. (When cons cells are used with lists, it's nicer to think of "car" and "cdr" as "first" and "rest". "First" holds whatever data you want the list to hold, like numbers, or even links to other lists. "Rest" holds the rest of the list. You can actually put whatever you want into the "rest" part, too, but we'll ignore that here.) "Nil" is the "empty list", which basically means "the list has ended!"

So, what if we wanted to tack a '0' onto the front again?

[0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil

See? We just created a new cons cell that pointed to the beginning of the old list. You'll hear people call this "consing" a value onto the front. But, you'll notice that the rest of the list is untouched.

Okay, but why does anyone want this? You can share lists. Imagine you wanted two basically identical lists. Only now you wanted one list to start with a '7', and the other with a '4'? Well, with the array-like way, we'd have to have two lists.

[ 7 0 1 2 3 4 5 6 ]
[ 4 0 1 2 3 4 5 6 ]

What if you replaced the '5' with '13', and share the change?

[ 7 0 1 2 3 4 13 6 ]
[ 4 0 1 2 3 4 5 6 ]

You have two totally separate lists. If you want to share the change, you'll have to make the change in both lists.

What happens with traditional Lisp lists? First, sticking a '7' and a '4' to the front:

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> nil
   /
[4]

Yup. We just made two conses that both point to the old list. The rest of the list is shared. And, if we replace '5' with '13':

[7]
   \
    ----> [0] -> [1] -> [2] -> [3] -> [4] -> [13] -> [6] -> nil
   /
[4]

Both lists get the change, because the rest is shared.

The point of all this is that, unlike what many folks expect, traditional Lisp lists aren't a single thing. They are a bunch of little things (conses) that point to each other to form a chain, which is the list. If you want to get the length of the chain, you have to follow all the little links until you get to the end, nil. Thus, O(n) length.

Lisp lists could be made O(1) if they were done like arrays. I'm sure some obscure Lisps do this, and get rid of linked lists (conses) altogether. But, conses seem to be one of the things that makes its way into basically every popular Lisp dialect. If you want O(1) length and lookup, most of them provide arrays or vectors, too.

---

Linked-list fun:

 -----------------<------------------------<----------
|                                                     |
 --> [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -->

This linked list eventually points to itself. If you use your length function, it will loop forever, looking for the end, but never finding it.

Answer 2

Most Lisp dialects don't have lists as a primitive data type. In Common Lisp for example lists are made of cons cells and the empty list (aka NIL). A cons cell is a data structure with two fields: CAR and CDR. With cons cells and NIL one can provide a lot of data structures: singly linked lists, assoc lists, circular lists, trees, ...

Lisp could have implemented lists in a different way (without conses), but generally it hasn't.

Btw., Common Lisp has adjustable arrays with fill pointer. The fill pointer provides the length in O(1).