Clojure rseq in Constant Time?

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?

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

I don't know how it's implemented, but I would think it just returns some object that implements sequence interface and knows how to traverse the structure (vector or sorted map) in reverse order. The result sequence is lazy, so it doesn't have to traverse the whole structure immediately.

It returns the new interface in constant time like Goran Jovic said but printing it out is linear. So displaying it in the REPL is linear, but putting it in a def is constant.