Clojure rseq in Constant Time?

Question

I was reading in Practical Clojure (Chapter 5) that the rseq function operation executes in constant time. It seems to me that it should be a linear time operation. Can anyone shed some light on this for me?

Answer 1

Try this:

(class [1 2 3 4])

You'll see:

clojure.lang.PersistentVector

Now try this:

(class (rseq [1 2 3 4]))

And the sequence implementation is different:

clojure.lang.APersistentVector$RSeq

As Roman said, it is a changed interface to a sequence. All the elements are where they were you are just accessing them in a reverse order.

You can see RSeq class to see how it's implemented here: https://github.com/clojure/clojure/blob/b578c69d7480f621841ebcafdfa98e33fcb765f6/src/jvm/clojure/lang/APersistentVector.java