Persistent data structures in Scala

Question

Are all immutable data structures in Scala persistent? If not, which of them are and which not? What are the behavioural characteristics of those which are persistent? Also, how do they compare to the persistent data structures in Clojure?

Answer 1

List, Vector, HashMap and HashSet are all persistent on Scala 2.8. There are other persistent data structures, but these covering all the major uses, I'm not sure there's any point in enumerating all of them.

Answer 2

Please have a look at these excellent articles by Daniel Spiewak:
http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala
http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

He's also referring to the Clojure implementation.

Answer 3

For the last part of your question, I remember Rich Hickey mentioning in a presentation that the Clojure data structures have been ported to Scala. Also, Michael Fogus mentions plans for Scala 2.8 to adopt some of Clojure's data structures in this interview.

Sorry this is so short on details... I'm not sure what the status is on the above mentioned Scala 2.8 plans, but I remembered Rich and Michael mentioning this and thought it might be an interesting thing for you to google for if you're interested.

Answer 4

Scala's immutable data structures are all persistent, in the sense that the old value is maintained by an `update' operation. In fact, I do not know of a difference between immutable and persistent; for me the two terms are aliases.

Two of Scala's 2.8 immutable data structures are vectors and hash tries, represented as 32-ary trees. These were originally designed by Phil Bagwell, who was working with my team at EPFL, then adopted for Clojure, and now finally adopted for Scala 2.8. The Scala implementation shares a common root with the Clojure implementation, but is certainly not a port of it.