Persistent data structures in Scala

data-structures scala clojure persistent
Abhinav Sarkar picture Abhinav Sarkar · Jun 24, 2010 · Viewed 10.2k times · Source

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

Martin Odersky picture Martin Odersky · Jun 24, 2010

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.

Related questions

Change priority of items in a priority queue

Using Scala 2.9 to implement a kind of Dijkstra algorithm (pseudo code) val queue = new PriorityQueue queue.insert(...) while (!queue.isEmpty) { val u = queue.extractMin queue.foreach { v => if (condition(u, v)) queue.decreaseKey(v, newPriority) } } I'd like to change …

Read More
What is the difference between Python's list methods append and extend?

What's the difference between the list methods append() and extend()?

Read More
How to remove a key from a Python dictionary?

When deleting a key from a dictionary, I use: if 'key' in my_dict: del my_dict['key'] Is there a one line way of doing this?

Read More