Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I manipulate a tree of immutable objects?

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:

  • Scene is a top-level object that contains a reference to a root Node.
  • Each Node can contain child Nodes and Ports.

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:

  • What is the best way to construct this hierarchy?
  • How would I replace an object that is arbitrarily deep in the object tree?
  • Is there a way to support back-links, e.g. a Node having a "parent" attribute?

And more generally:

  • Have any patterns emerged for dealing with this type of data?
  • Is there (academic) literature available on the subject?
  • Is this a good idea?
like image 707
Frederik Avatar asked Apr 06 '10 17:04

Frederik


People also ask

Can you change values of an immutable object?

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.

How do you edit immutable?

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.

What does it mean by saying immutable objects?

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.


1 Answers

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

like image 144
Daniel C. Sobral Avatar answered Nov 15 '22 23:11

Daniel C. Sobral