Warty Lists in Clojure

Summary: Lists are kind of warty in Clojure. Care should be taken, especially by those coming from other Lisps.

One of the things that still trips me up in Clojure is the actual types of lists. I used to program in Common Lisp, where things are a bit easier to understand: something is either a list or an atom. Lists are built out of conses and end with nil. Everything else is an atom.

Coming from Common Lisp, one might expect this to work:

=> (listp (cons 1 nil))

In CL, it will be true. In Clojure, it is also true. (Try it out yourself!) Launch a REPL. Go to Try Clojure.

=> (list? (cons 1 nil))

What about this:

=> (list? (cons 1 (cons 1 nil)))

We're consing onto a list, should be a list, no?

In Common Lisp, yes. In Clojure?


That's not a list. Go ahead, try it at your Clojure REPL.

What gives? How is that possible? Are we living in a Kafkaesque ECMAScript World?

Well . . . probably.

What's going on? Put on your Indiana Jones fedora. We're going on an adventure deep into the heart of the Clojure JVM implementation.

First, how is list? defined?

In clojure.core:

(defn list?
  "Returns true if x implements IPersistentList"
  {:added "1.0"}
  [x] (instance? clojure.lang.IPersistentList x))

Great, list? is just an instance check. What classes implement clojure.lang.IPersistentList? According to the javadoc on the Clojure sources, there are two: PersistentQueue and PersistentList. There's also a static inner class in PersistentList called EmptyList.

Let's see those at the REPL:

=> (type ())
=> (list? ())

=> (type (list 1 2 3))
=> (list? (list 1 2 3))

=> (type clojure.lang.PersistentQueue/EMPTY)
=> (list? clojure.lang.PersistentQueue/EMPTY)

These all return true when given to list?. What about (cons 1 nil)?

=> (type (cons 1 nil))
=> (list? (cons 1 nil))

Great. Consing onto nil gives you a list. Let's cons onto a list:

=> (type (cons 0 (list 1 2 3)))
=> (list? (cons 0 (list 1 2 3)))

Oh, no! Why does consing onto nil create a list, but consing onto a list create a cons? Poisonous dart averted! Back to the source code!

In clojure.core:

 ^{:arglists '([x seq])
    :doc "Returns a new seq where x is the first element and seq is
    the rest."
   :added "1.0"}

 cons (fn* cons [x seq] (. clojure.lang.RT (cons x seq))))

So it calls clojure.lang.RT/cons. We can look that up:

static public ISeq cons(Object x, Object coll){
    //ISeq y = seq(coll);
    if(coll == null)
        return new PersistentList(x);
    else if(coll instanceof ISeq)
        return new Cons(x, (ISeq) coll);
        return new Cons(x, seq(coll));

Wow! The code is clear: if the second argument is null (nil), it makes a PersistentList. Otherwise, it constructs a clojure.lang.Cons, which is not a list! We're at the root of our wart, but there's nothing we can really do about it except keep exploring.

If I have a list (according to list?) and I want to add an element to the front to make a new list, how do I do that?

Well, the answer is a little disappointing:

=> (def ls (list 1 2 3))
=> (def ls2 (conj ls 0))
=> (list? ls2)

conj will maintain the type, cons will not. What happens if I conj onto a Cons?

=> (def c (cons 1 (cons 2 nil)))
=> (conj c 0)
  (0 1 2)
=> (type (conj c 0))

So, there you have it. It's a bit of a wart having all of these slightly different types and predicates like list? that slice them up in odd ways. Sometimes it's like running away from a giant paper-mache ball.

In Clojure's defense, I will say that I rarely use list?, if at all. It's not a very useful function in clojure.core. I'm usually working at a much higher level than that, thinking in terms of sequences (an abstraction), not their concrete implementations. And in the end, you never get out of danger.

There you have it. If you'd like to learn more Clojure, I have a nice video series.