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?
Add a comment
|
4 Answers
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.
4 Comments
j-g-faustus
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.
Garrett Rowe
I don't think that data sharing (as opposed to copying) is a prerequisite for persistence as the term is normally used. (en.wikipedia.org/wiki/Persistent_data_structure)
Paweł Prażak
I found this paragraph in akka.io/docs/akka/1.2/scala/stm.html: "Scala provides so-called persistent datastructures which makes working with immutable collections fast. They are immutable but with constant time access and modification. They use structural sharing and an insert or update does not ruin the old structure, hence “persistent”. Makes working with immutable composite types fast. The persistent datastructures currently consist of a Map and Vector." - I find it a bit puzzling in light of this answer. I probably just misunderstood something.
Alex D
"Persistent" means that when you "modify" one of these structures (e.g. insert a key/val into a map), the performance guarantees provided by the original data structure also apply to the derived data structure. It is easy to construct an implementation where this is not the case.
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.
Comments
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.
answered Jun 24, 2010 at 15:15
Daniel C. Sobral
298k88 gold badges508 silver badges688 bronze badges
2 Comments
Martin Konicek
Does this mean that the + method of HashMap is O(1)?
Daniel C. Sobral
@MartinKonicek "Effective" O(1), which means some assumptions must hold for it to be O(1). See the collections performance characteristics docs.
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.
