In Clojure, when should I use a vector over a list, and the other way around?

Once again, it seems I've answered my own question by getting impatient and asking it in #clojure on Freenode. Good thing answering your own questions is encouraged on Stackoverflow.com :D

I had a quick discussion with Rich Hickey, and here is the gist of it.

[12:21] <Raynes>    Vectors aren't seqs, right?
[12:21] <rhickey>   Raynes: no, but they are sequential
[12:21] <rhickey>   ,(sequential? [1 2 3])
[12:21] <clojurebot>    true
[12:22] <Raynes>    When would you want to use a list over a vector?
[12:22] <rhickey>   when generating code, when generating back-to-front
[12:23] <rhickey>   not too often in Clojure

If you've done Java programming a lot, and are familiar with the Java collection framework, think of lists like LinkedList, and vectors like ArrayList. So you can pretty much choose containers the same way.

For further clarification: if you intend to add items individually to the front or the back of the sequence a lot, a linked list is much better than a vector, because the items don't need to be shuffled around each time. However, if you want to get at specific elements (not near the front or back of the list) frequently (i.e., random access), you will want to use vector.

By the way, vectors can easily be turned into seqs.

user=> (def v (vector 1 2 3))
#'user/v
user=> v
[1 2 3]
user=> (seq v)
(1 2 3)
user=> (rseq v)
(3 2 1)

Vectors have O(1) random access times, but they have to be preallocated. Lists can be dynamically extended, but accessing a random element is O(n).

When to use a vector:

Indexed access performance - You get ~O(1) cost for indexed access vs. O(n) for lists

Appending - with conj is ~O(1)

Convenient notation - I find it both easier to type and to read [1 2 3] than '(1 2 3) for a literal list in circumstances where either would work.

When to use a list:

When you want to access it as a sequence (since lists directly support seq without having to allocate new objects)

Prepending - adding to the start of a list with cons or preferably conj is O(1)

just a quick side note:

"I read that Vectors are not seqs, but Lists are."

sequences are more generic than either lists or vectors (or maps or sets). Its unfortunate that the REPL prints lists and sequences the same because it really makes it look like lists are sequences even though they are different. the (seq ) function will make a sequence from a lot of different things including lists, and you can then feed that seq to any of the plethora of functions that do nifty things with seqs.

user> (class (list 1 2 3))
clojure.lang.PersistentList

user> (class (seq (list 1 2 3)))
clojure.lang.PersistentList

user> (class (seq [1 2 3]))
clojure.lang.PersistentVector$ChunkedSeq

Sec has a shortcut that returns its argument if it is already a seq:

user> (let [alist (list 1 2 3)] (identical? alist (seq alist)))
true
user> (identical? (list 1 2 3) (seq (list 1 2 3)))
false

static public ISeq seq(Object coll){
        if(coll instanceof ASeq)
                return (ASeq) coll;
        else if(coll instanceof LazySeq)
                return ((LazySeq) coll).seq();
        else
                return seqFrom(coll);
}

lists are sequences, though other things are as well, and not all sequences are lists.