Immutable Data Structures

One of the key practices enabling referential transparency, local reasoning, composability, reuse and performance of functional programming is immutability. Data once created remain immutable for its entire lifecycle, which allow them to be safely shared between processing threads, without worrying about acquiring and releasing shared mutex locks and waiting. In the functional world an integer value of 1 or a boolean value of true or a complex data structure that represents a ticker symbol and its pricing history are all perpetually immutable.

However, how does that work in real world? In real world, data does change over time. Let us say, we have a singly linked list, and we want to replace the head of the list. How do we achieve that using data sharing? There are two options.

1. Pessimistic data copying, which has huge performance and concurrency issues
2. Data sharing, which will look in detail below

Data Sharing

For the purpose of our example we will look at our own simple linked list of integers as shown below,

scala> sealed trait List
defined trait List
scala> case object Empty extends List
defined object Empty
scala> case class NonEmpty(h: Integer, t: List) extends List
defined class NonEmpty
scala> val l = NonEmpty(1, NonEmpty(2, NonEmpty(3, Empty)))
l: NonEmpty = NonEmpty(1,NonEmpty(2,NonEmpty(3,Empty)))

We have a simple singly linked list, which is ordered implemented using a sealed trait and two case implementation. One representing a singleton empty instance and a non empty type, which is basically a head element and a tail list. Then we constructed a list of three elements. Now let us look at defining a function, that replaces the head of the list, using data sharing.

scala> def replace(i: Integer, l: List) = l match {
     | case Empty => sys.error("No head for empty list")
     | case NonEmpty(_, tail) => NonEmpty(i, tail)
     | }
replace: (i: Integer, l: List)NonEmpty
scala> val l1 = replace(5, l)
l1: NonEmpty = NonEmpty(5,NonEmpty(2,NonEmpty(3,Empty)))

The replace function, pattern matches on a non empty list, and ignores its head and returns a new nonEmpty instance with the passed value as the head, but more importantly staring the tail with the old list instance. This is perfectly acceptable, as since the tail is immutable, it can be safely shared between the two list instances. Also, the whole replace operation is constant in time and memory, regardless of the length of the list.

Of course, this is may not always be the case, some operations may require you to implement in such a way that they are proportional to the length of the list. Imagine, how one would implement a function that will drop the last element of the list? The key here is where necessary, use mutable structures internally to address performance issues, but to maintaining the API into the data structure entirely immutable.