clojure: no cons cells

In Common Lisp, a list is a sequence of cons cells. Each cons cell has two slots or pointers, called the "car" and "cdr". The car points to (or holds) something--anything. The cdr usually points to either another cons cell, or nil. nil counts as the end of the list. Clojure gives you roughly the same functionality with its lists, but the underlying representation is different. It does have a data type called Cons, but not all lists or all parts of a given list are built from Conss. (Now you should read jmargolisvt's answer if you haven't already.) [EDIT: Other answers show that what I say here about the relationship between lists and Conses in Clojure is incorrect. One might feel that it's correct in an informal sense of "list"--or not.]

Also note that partly because of the sequence abstraction idea, lists per se are much less common in Clojure than in Common Lisp or Scheme. However, other kinds of sequences are very common.

It's also worth knowing that in Clojure you can't assume that something that looks like a list when you print it out is actually a list. It might be a lazy sequence, for example, which is not considered a list.

Here are some potentially informative Clojure examples using lists:

user=> (def foo (list 1))
#'user/foo
user=> foo
(1)
user=> (class foo)
clojure.lang.PersistentList
user=> (def bar (cons 2 foo))
#'user/bar
user=> bar
(2 1)
user=> (class bar)
clojure.lang.Cons

(Both foo and bar are considered lists, even though class returns different data types.)

user=> (next bar)
(1)
user=> (rest bar)
(1)
user=> (class (next bar))
clojure.lang.PersistentList
user=> (class (rest bar))
clojure.lang.PersistentList
user=> (next foo)
nil
user=> (rest foo)
()
user=> (= nil ())
false
user=> (rest ())
()
user=> (rest nil)
()
user=> (next ())
nil
user=> (next nil)
nil

In Common Lisp, you can cons an object onto another object other than a list or nil. The result is a a "dotted list" (1 . 2), which is a single cons cell in which the cdr pointer points to something other than another cons cell or nil, as it would in a normal list. Let's try that in Clojure:

user=> (cons 1 2)
IllegalArgumentException Don't know how to create ISeq from: java.lang.Long  clojure.lang.RT.seqFrom (RT.java:528)

While I'm at it, one more striking difference with Common Lisp (in which nil = () = false):

user=> (= nil false)
false
user=> (= () false)
false

However, even though nil is not false, you can use it like false:

user=> (if nil "nil works like true" "nil works like false")
"nil works like false"

You can't do that with the empty list, however:

user=> (if () "() works like true" "() works like false")
"() works like true"

(Despite these examples, on the whole Clojure is much simpler and more elegant than Common Lisp, IMO. Even people who also love Common Lisp--as I do--must admit that Common Lisp is neither simple nor elegant. It has its own kind of beauty.)

According to this page from clojure.org:

cons, first and rest manipulate sequence abstractions, not concrete cons cells

Clojure lists do not end with an empty list and they are not traditional cons cells. They are data structures that implement sequencing. This page on programming to abstractions explains Clojure's approach to "seqable" structures, including lists:

In general, programming to abstractions gives you power by letting you use libraries of functions on different data structure regardless of how those data structures are implemented.

So Clojure lists are like cons cells in that they implement cons, first, and rest but that only means they share a common interface. Their underlying implementations differ, but they are both "seqable".

Lisp provides a primitive cons data structure and a notation for it.

See John McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, 1960, Chapter 3, Recursive Functions of Symbolic Expressions.

That chapter introduces:

• Symbolic expressions made of atoms and pairs of symbolic expressions written using a dot notation: ( a . b )
• a list notation to abbreviate certain symbolic expressions (a b c)
• an atomic symbol nil to terminate lists
• the primitive functions car, cdr, cons, eq and atom
• several other functions: ff, subst, equal, null, cadr, caddr, null, append, among, pair, assoc, sublis, apply, eval, ...

Early on in Lisp, functions to mutate cons cells have been added: rplaca (means replace car) and rplacd (means replace cdr). See the LISP 1.5 Programmer's Manual by John McCarthy et al. from 1962. These functions allow us to write destructive functions and also allow us to create cyclic cons-based data structures like cyclic lists.

Common Lisp

Typically Lisp dialects implement most of this. Common Lisp is no exception and for it this functionality is described in the Common Lisp standard: Conses. Examples using the functions mentioned above:

; pair two lists into a list of cons cells.
; the function pair is called pairlis in Common Lisp.
CL-USER 17 > (pairlis '(john mary eva) '(34 29 40))
((EVA . 40) (MARY . 29) (JOHN . 34))

; find a cons cell in a list of cons cells,
; based on the content of the car of those cons cells
CL-USER 18 > (assoc 'eva (pairlis '(john mary eva)
                                  '(34 29 40)))
(EVA . 40)

; create a tree out of cons cells and atoms
CL-USER 19 > (cons (cons 10 20) (cons 30 40))
((10 . 20) 30 . 40)

; a cons cell is not an atom
CL-USER 20 > (atom (cons 1 2))
NIL

; a cons cell is not nil
CL-USER 21 > (null (cons 1 2))
NIL

; substitute an item with a new one in a tree
CL-USER 22 > (subst 30                          ; new
                    'bar                        ; old
                    '((10 . 20) . (bar . 40)))  ; tree
((10 . 20) 30 . 40)   ; also written as  ((10 . 20) . (30 . 40))

; substitute several items in a tree, using an assoc list
; to describe the substitutions
CL-USER 23 > (sublis '((a . 10) (d . 40))      ; substitutions
                     '((a . b) . (c . d)))     ; tree
((10 . B) C . 40)

Lists are then a special case of symbolic expressions. They are typically written without dots:

CL-USER 24 > '(a . (b . nil))
(A B)

Common Lisp also supports the mutating operations rplaca and rplacd of Lisp 1.5:

CL-USER 25 > (let ((c (cons 0 1)))              ; create a cons
               (print c)                        ; print it
               (print (rplaca c 'foo))          ; replace the car
               (print (rplacd c 'bar))          ; replace the cdr
               (print (eq c (rplaca c 'baz)))   ; identical ?
               (values))
(0 . 1)      ; the cons cell
(FOO . 1)    ; car replaced
(FOO . BAR)  ; cdr replaced
T            ; still the same object

Emacs Lisp

Emacs Lisp also implements the above functionality:

ELISP> (sublis '((a . 10) (d . 40))                                             
               '((a . b) . (c . d)))
((10 . b) c . 40)

Clojure

Clojure does not support these symbolic expressions as described by John McCarthy. It has no cons cells, no dot notation and does not provide the above interface. For example atom means something completely different in Clojure. cons does not create a cons cell. Lists are not made of cons cells.

In Clojure a dot is just another symbol:

user=> (count '(1 . 2))
3

There is a primitive function to construct lists:

user=> (list 1 2 3)
(1 2 3)

The result should be a list:

user=> (list? (list 1 2 3))
true

There is a function called cons:

user=> (cons 0 (list 1 2 3))
(0 1 2 3)

Somehow this is not a list:

user=> (list? (cons 0 (list 1 2 3)))
false

Basically Clojure does use different data structures (-> sequences, logical lists) with its own naming and semantics. Even if names are similar to Lisp names, don't expect that they do the same.

Scheme

The programming language Scheme also provides cons cells similar to above. It lacks some of the functions, but they can be easily implemented. For example sublis might be implemented like this in Scheme (see initdr.scm):

(define (sublis alist tree)
  (if (pair? tree)
      (cons (sublis alist (car tree))
            (sublis alist (cdr tree)))
      (if (assv tree alist)
          (cdr (assv tree alist))
          tree)))

• Clojure does have a cons structure: clojure.lang.Cons.
• It is used for the results of cons calls
• ... and nothing else: neither lists, nor vectors, nor lazy sequences of any kind.
• Nor can it be used for pairs of objects in general: the tail/rest/cdr is a sequence, not an Object.
• If you cons something onto a list, a vector, or a lazy sequence, you get a Cons.
• But, as the other answers make plain, there are no functions that deal in Conses. They all deal in sequences in general.

One other use: conjing onto an indeterminate sequence (neither vector list nor set nor map ...) yields a Cons.