For those of you playing along at home, this is because of Clojure's reducers framework [1]. If we were to extend 'clojure.core.protocols.CollReduce' to ArrayList, we'd get similar performance, but the important point is that efficient iteration across immutable collections is very much possible.
http://clojure.com/blog/2012/05/08/reducers-a-library-and-mo...
EDIT: and my response is just a little redundant now
Are you sure? Reducers framework has its own version of major functions (map, reduce, etc.) and has to be called explicitly by use or require.
Last time I checked, in version 1.5, if you just call normal reduce, it does not use reducers framework.
there were changes to the core data structures in order to support reducers, namely the addition of polymorphic reduction by the collection. See: https://github.com/clojure/clojure/commit/5b281880571573c591...
It was a pretty transparent change.
As far as Clojure iteration is concerned, Vectors (immutable, persistent) are actually faster than ArrayLists (mutable, unsynchronized). Criterium reports:
Amusingly, using iterators directly instead of reduce speeds up ArrayLists (since there's no need to go through seq, I think), and slows down Vectors to the same speed: After conferring with ztellman, I suspect this is due to Clojure's InternalReduce avoiding extra iterator allocations over vectors, since it can recur f directly over the internal array at each leaf node.