I'm building an entire application out of immutable objects so that multi-threading and undo become easier to implement. I'm using the Google Collections Library which provides immutable versions of Map, List, and Set.
My application model looks like a tree:
An object graph might look like this:
Scene
|
+-- Node
|
+-- Node
|
+- Port
+-- Node
|
+- Port
+- Port
If all of these objects are immutable, controlled by a top-level SceneController object:
And more generally:
You can't change the value of an immutable object. That is literally what the English word "immutable" means: unchangeable. The whole point of functional programming is that you never change objects, you only return new ones.
Immutable objects are objects that don't change. You make them, then you can't change them. Instead, if you want to change an immutable object, you must clone it and change the clone while you are creating it.
In object-oriented and functional programming, an immutable object (unchangeable object) is an object whose state cannot be modified after it is created. This is in contrast to a mutable object (changeable object), which can be modified after it is created.
There are two concepts of interest here. First, persistent data structures. If all elements of the tree are immutable, then one can derive a new tree from the original tree by replacing some parts, but referring to the older parts, thus saving time and memory.
For example, if you were to add a third Port to the Node that has two ports already, you'd have to create a new Scene, a new Scene's Node's descendant, and the Node that you are changing. The other Node and all of the Ports do not need to be created anew -- you just refer to them in the new Scene/Nodes.
The other concept is that of a Zipper. A zipper is a way to "navigate" through a persistent data structure to optimize local changes. For instance, if you added four new Ports instead of just one, but you added each Port one at a time, you'd have to create four new Scenes, and eight new Nodes. With a zipper, you defer such creations until you are done, saving up on those intermediary objects.
The best explanation I ever read about zipper is here.
Now, use of a zipper to navigate a data structure remove the need to have back-links. You can have back-links in an immutable structure, by clever use of recursive constructors. However, such a data structure would not be persistent. Non-persistent immutable data structures have lousy modification performance, because you need to copy the whole data each time.
As for academic literature, I recommend Purely Function Data Structures, by Okasaki (dissertation PDF, fully fledged book).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With