How Immutability is Implemented

Question

I am trying to grasp how the trie and such in immutability is implemented, as relates to immutability in JS. I understand how there is supposed to be significant structural sharing.

My question is say you have a graph sort of structure like this:

a -- b
     |
     c
     |
     d -- h
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

So then you add an x to the system. I'll try it two different ways:

a -- b
     |
     c
     |
     d -- h -- x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

That one is just added as a leaf node.

a -- b
     |
     c
     |
     d -- h
          |
          x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n

That one is added in the middle of a path.

I am wondering what the immutable data structure would be to handle these 2 situations. So essentially we have a function f : graph -> graph' that changes the graph into a "new graph", when under the hood it should only be making a small adjustment to the data structure. Not sure how this would look or how it works. My first attempt at an explanation would be something like this...

It starts of in a wrapper object which is like ImmutableJS's API layer on top of the JS objects.

 --------------------------
|                          |
|    a -- b                |
|         |                |
|         c                |
|         |                |
|         d -- h           |
|              |           |
|         e -- i -- l      |
|              |           |
|         f -- j -- m      |
|              |           |
|         g -- k -- n      |
|                          |
 --------------------------

Then you make the change and it creates a new wrapper object.

 --------------------------           --------------------------
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

Then likewise for the second example:

 --------------------------           -------------------------- 
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h           |         |                          |
|              |           |         |                          |
|              o --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------

The boxes are the API objects you use, and the graphs inside are the plain JS data objects.

But in these examples the original graph structure is modified (placing a link to h in the first example, and placing an o placeholder in the second one). So I'm wondering how specifically you would make these things immutable. Every change I make to the graph I would like to "return a new object", but under the hood there is optimal structural sharing.

Thank you for your help.

Answer 1

The example in case of trie is not a general solution for immutability, it's just a way of representing an array in a tree then applying general solutions for persistent trees.

Following are general solutions for persistent graphs

1. Fat node.
   Each node stores history of it's changes and timestamp of those changes. When looking for a graph at specific point in time, we provide the timestamp to get version at that time. It's space efficient (only new value is stored) however access time suffers in this case due to an additional search (Mulplicative slowdown) on the modification array (of arbitrary length) for each node.

2. Path copying
   In this case we create a new node keeping all the children, we create a new node for each node in it's path to root. In this case we have to store an array of roots. It's access time is same as original graph, only extra time that it takes is due to search on the root array (Additive slowdown). This is what's being used in the trie example. It's space inefficient as every change creates a set of new nodes with new root, representing path to new node from new root.

3. Modification Box(Sleator, Tarjan et al)
   This one combines both Fat node and Path copying. Every node can store only one modification. If we try to update an already modified node then we use path copying and try to create a duplicate node with duplicate path to it. Interestingly while creating new path we'll have to take care of modification boxes. In the new path only those nodes are duplicated which have been already modified, else only there modification boxes are updated.

Note: Path copy and Modification box are application to trees (or may be DAGs) and not not generic graphs. As both of these involve cascading creation of new nodes from mdoified node to root. A generic graph doesn't have a root. So only method available to us is Fat Node for generic graphs.

Ref:
1. https://en.wikipedia.org/wiki/Persistent_data_structure
2. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/persistent.pdf

Fat Node

Following structure of Node and Graph should suffice

Node ->
    var value;
    Node parent
    Node[] children
    Modification[] modifications
Modification ->
    Node node
    Date timestamp

Graph -> (Adjancency list)
    {
        'a': [b],
        'b': [c],
        'c': [d],
        'd': [h],
        'e': [i],
        'f': [j],
        'g': [k],
        'h': [d, i],
        'i': [e, j, l],
        'j': [f, i, k, m],
        'k': [g, j, n],
        'l': [i],
        'm': [j],
        'n': [k],
    }

Fat Node Case 1

Fat Node Case 2

Path Copy

If graph in your example is a tree with node a as root, then path copy will work same as described in trie example

Following simple tree nodes with root array will suffice

Node ->
    var value
    Node parent
    Node[] children

Graph ->
    roots: [
        {
            Node root1,
            Date timestamp
        },
        {
            Node root2,
            Date timestamp
        }
        ...
    ]

Since node h is being modified, entire path from node h to root node a would be duplicated.

Path copy Case 1

Path Copy Case 2

Modification Box

Assuming the graph in example is tree, following would suffice

Node ->
    var value
    Node parent
    Node[] children
    ModificationBox modBox

ModificationBox ->
    timestamp,
    Attribute {
        type: value/parent/children[i] etc (only one attribute)
        value: value of attribute
    }


Graph ->
    roots: [
        {
            Node root1,
            Date timestamp
        },
        {
            Node root2,
            Date timestamp
        }
        ...
    ]

Modification Box Case 1

Node h is not modified

Modification Box Case 2

For this case lets assume that h has already been modified