Learning Functional Data Structures and Algorithms

Persistent data structures

If we follow the second copy-as-much-needed-and-share strategy, a thread holding a reference to the original lists will never be surprised by any changes. From the thread's point of view, nothing has changed and things continue as before.

However, the change needs to happen somewhere. How else would we grow/shrink data structures? The change does indeed happen, but only at creation time.

Let's look at what we mean when we say creation time. Consider the following snippet:

scala> :paste 
 
@scala.annotation.tailrec 
def print(low: Int, high: Int): Unit = 
  if (low > high) 
    println("Done") 
  else { 
    println(low) 
    print(low+1, high) 
  } 
scala> print(1, 10) 
1 
2 
... 
10 
Done 

We are printing a range of numbers. As we know, this needs some ...