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?
5 Answers
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
-
1While you're on freenode, come to the dark side and join #stackoverflow! :-P Jul 18, 2009 at 17:31
-
I actually used to idle there. I switched IRC clients and never thought to add #stackoverflow to my autojoin list.– RayneJul 18, 2009 at 18:19
-
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?) Feb 25, 2014 at 8:00
-
31This 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. Feb 25, 2014 at 20:58
-
25@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".– omielApr 4, 2014 at 5:14
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 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.– RayneJul 18, 2009 at 17:25
-
1I will edit my post to say, vectors can be made into seqs, via the seq function. :-) Jul 18, 2009 at 17:26
-
2Chose 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. :)– RayneJul 18, 2009 at 17:32
-
A deque is better than a linked list in the case of adding first and last. LLs are pretty terrible :P– boxedDec 24, 2013 at 10:02
-
1@boxed You cannot implement a deque on top of a vector or
ArrayList
without, effectively, reimplementingArrayDeque
yourself. Jan 20, 2015 at 15:36
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).
-
3Technically, 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. :-) Jul 18, 2009 at 17:20
-
4("Linked list" as described above refer to doubly-linked lists. Singly-linked lists have O(1) access to the front element only. :-P) Jul 18, 2009 at 17:21
-
1As 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. Jun 19, 2014 at 18:16
-
@ChrisJester-Young Single-linked list can support O(1) access to the back if it stores a reference to the back element, like that. May 10, 2015 at 21:25
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)
-
3Even 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– boxedDec 24, 2013 at 10:00
-
2Re: the
~O(1)
, for those to whom this cost explanation might be helpful - stackoverflow.com/questions/200384/constant-amortized-time Mar 29, 2016 at 10:11
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.
-
I dont mean to pick on a small point, its just an opportunity to point out somthing useful. many will already know this :) Jul 20, 2009 at 22:28
-
2
-
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 writeclass
notclass?
. Oct 25, 2013 at 10:22 -
-
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? Jan 3, 2014 at 5:21