Menu
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?
866
A data structure is said to be persistent if it is capable to maintaining its previous updates as separate versions and each version can be accessed and updated accordingly. It makes the data structure immutable and thread safe. For example, String class object in Java is immutable.
A Data Structure in scala is a type of data structure that aids in the storage, organisation, and retrieval of data in the field of computing in general. It is important to note that Scala distinguishes between immutable and mutable collection data types. Mutable collections are organise under the scala.
The data structure is fully persistent if every version can be both accessed and modified. If there is also a meld or merge operation that can create a new version from two previous versions, the data structure is called confluently persistent. Structures that are not persistent are called ephemeral.
With a queue, it's important to maintain linear structure but still maintain the ability to modify both ends of the queue. We cannot do this through a straightforward translation of the non-persistent structure. One approach is to “buffer” items added onto the end of the queue until they are needed.
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.
94
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.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
