26

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?

Abhinav Sarkar
  • 23,534
  • 11
  • 81
  • 97

4 Answers4

63

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
  • 20,470
  • 9
  • 51
  • 49
  • 26
    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 Jun 24 '10 at 10:33
  • 2
    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 Jun 24 '10 at 19:52
  • 5
    I found this paragraph in http://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. – Paweł Prażak Oct 31 '11 at 11:23
  • 4
    "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. – Alex D May 25 '14 at 05:10
9

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
  • 14,197
  • 5
  • 32
  • 32
6

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 C. Sobral
  • 295,120
  • 86
  • 501
  • 681
  • Does this mean that the + method of HashMap is O(1)? – Martin Konicek Dec 02 '12 at 14:03
  • 2
    @MartinKonicek "Effective" O(1), which means some assumptions must hold for it to be O(1). See the collections [performance characteristics](http://docs.scala-lang.org/overviews/collections/performance-characteristics.html) docs. – Daniel C. Sobral Dec 03 '12 at 01:34
4

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
  • 83,634
  • 13
  • 201
  • 212