O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required