Learning Functional Data Structures and Algorithms

Copy-on-write

What if we have never mutated data? When we need to update, we could copy and update the data. Consider the following Scala snippet:

scala> val x = 1 to 10 
x: scala.collection.immutable.Range.Inclusive = Range(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) 
 
scala> x  map (_ / 2) filter ( _ > 0 ) partition ( _ < 2 ) 
res4: (scala.collection.immutable.IndexedSeq[Int], scala.collection.immutable.IndexedSeq[Int]) = (Vector(1, 1),Vector(2, 2, 3, 3, 4, 4, 5)) 

Here is a figure showing all of the copying in action:

This is copy-on-write semantics: we make a new data structure every time a change happens to the original data structure. Note the way the filter ...