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?
+2
A:
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.
Michał Marczyk
2010-06-24 04:28:15
+6
A:
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.
Michel Krämer
2010-06-24 05:17:25
+10
A:
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.
Martin Odersky
2010-06-24 08:43:18
Well, my understanding is that "persistent" refers to an implementation where updating an immutable value returns a value that shares sub-structure with the original rather than making a full clone. This can give immutable collections with performance close to their mutable counterparts - you don't need to copy 10k old elements in order to add a single new one.
j-g-faustus
2010-06-24 10:33:56
I don't think that data sharing (as opposed to copying) is a prerequisite for persistence as the term is normally used. (http://en.wikipedia.org/wiki/Persistent_data_structure)
Garrett Rowe
2010-06-24 19:52:54
+1
A:
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.
Daniel
2010-06-24 15:15:52