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

Question

I read that Vectors are not seqs, but Lists are. I'm not sure what the rationale is for using one over the other. It seems that vectors are used the most, but is there a reason for that?

Spray

Related #6928827 – Euphemism

Answer 1

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

Spray

While you're on freenode, come to the dark side and join #stackoverflow! :-P – Bloater

I actually used to idle there. I switched IRC clients and never thought to add #stackoverflow to my autojoin list. – Spray

I'm a Lisp newbie, but I wondered whether vectors, maps and sets break in some way the idea that all code is interchangeable with data? Or is this just one of those things that makes Clojure a practical Lisp? (OR, can you evaluate a vector?) – Regime

This is completely unhelpful chat snippet. "Generating code" "generating back-to-front" -> means precisely?? I am really having difficulty with this question because in my book laziness + declarative style = far better performance, and yet vectors are suggested everywhere in Clojure which leaves me totally confused. – Stricklin

@JimmyHoffa The way I understand it: "Generating Code" = "Inside a Macro" (because most of the code is function calls, thus lists) ; "generating back to front" = "building a sequence by prepending". – Filigree

@RobertGrant Clojure code is composed of vectors and maps too. For example, a function's argument list (hum) is a vector. – Filigree

I agree this answer is not very good. A good answer should contain big O notation of things like accessing a element by index, getting the count, appending element and modifying the data structure by index. – Irruption

Answer 2

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)

Bloater

Vectors aren't seqs, but they are sequential. (source: Rich himself on #clojure on freenode.) Also, I don't really know Java at all, but Rich did just answer my question. – Spray

I will edit my post to say, vectors can be made into seqs, via the seq function. :-) – Bloater

Chose your answer because it did indeed answer the question, and I really don't like choosing my own answers as correct. Doesn't seem right. Thanks. :) – Spray

A deque is better than a linked list in the case of adding first and last. LLs are pretty terrible :P – Tisza

@Tisza Yes, but deques are not built in to Clojure, whereas lists and vectors are. – Bloater

@Tisza In Java LinkedList<E> implements the Deque<E> interface. Afaik using linked lists is standard for creating deques. – Reword

@LucasHoepner maybe standard. Also almost always the wrong thing to do. ESPECIALLY in java when the contained objects themselves aren't inlined into the node (like in C++ or whatever). Linked lists in this case take more memory, more CPU/is slower. It's quite simple to implement a deque on top of a vector/ArrayList too so that it's not in the standard clojure lib seems irrelevant. – Tisza

@Tisza You cannot implement a deque on top of a vector or ArrayList without, effectively, reimplementing ArrayDeque yourself. – Bloater

Answer 3

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).

Waldenburg

Technically, linked lists have O(1) access times...if you're accessing the front or back element only. :-P However, vectors do have O(1) random access. :-) – Bloater

("Linked list" as described above refer to doubly-linked lists. Singly-linked lists have O(1) access to the front element only. :-P) – Bloater

As someone just diving into Clojure, this is a WAY better answer than the other two with more votes. The other two tell me nothing of use. – Acidosis

@ChrisJester-Young Single-linked list can support O(1) access to the back if it stores a reference to the back element, like that. – Judaic

I think Vectors in Clojure are not implemented as linked lists. Looking here into the docs they say that the access is O(log32N). clojure.org/reference/… – Durward

Answer 4

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)

Rohr

Even when adding/removing at both ends a list is a pretty terrible choice. A deque is much better (in CPU and especially memory). Try github.com/pjstadig/deque-clojure – Tisza

Re: the ~O(1), for those to whom this cost explanation might be helpful - https://mcmap.net/q/21106/-what-is-constant-amortized-time – Miscegenation

The access is described as O(log32N) in the clojure docs clojure.org/reference/… – Durward

Note that technically although some of these would be O(log32 N) if N could grow to infinity, in practice this is equivalent to O(1) in Clojure because N is bounded to a fixed maximum size (int) – Rohr

Answer 5

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.

Pitchford

I dont mean to pick on a small point, its just an opportunity to point out somthing useful. many will already know this :) – Pitchford

Don't you mean class instead of class?? – Janenejanenna

Not sure if your example has changed following clojure updates (I think I'm on 1.5), but both your examples return clojure.lang.PersistentList for me. I'm assuming you meant to write class not class?. – Bausch

I did indeed! I'll fix that – Pitchford

Still a tad confused; since class returns the same PersistentList for both of these expressions you mentioned, this implies that sequences and lists are indeed the exact same thing? – Hindu

there is a short cut in sec which returns it's argument if it's already a sequence. so seq is returning it's argument back in the example above. I'll put the code for this in the answer. – Pitchford

Very helpful. I didn't realize that seq returned a wrapped vector. However, I think it's good that it displays it using parens, since the returned object is treated by conj the same way as a list. But the real problem is the sneaky, silent switching of semantics. "conj considered harmful" – Bedaub