How Immutability is Implemented : <p>I am trying to grasp how the <a href="https://hackernoon.com/how-immutable-data-structures-e-g-immutable-js-are-optimized-using-structural-sharing-e4424a866d56" rel="noreferrer">trie</a> and such in immutability is implemented, as relates to immutability in JS. I understand how there is supposed to be significant structural sharing.</p>

<p>My question is say you have a graph sort of structure like this:</p>

<pre><code>a -- b
     |
     c
     |
     d -- h
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n
</code></pre>

<p>So then you add an <code>x</code> to the system. I'll try it two different ways:</p>

<pre><code>a -- b
     |
     c
     |
     d -- h -- x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n
</code></pre>

<p>That one is just added as a leaf node.</p>

<pre><code>a -- b
     |
     c
     |
     d -- h
          |
          x
          |
     e -- i -- l
          |
     f -- j -- m
          |
     g -- k -- n
</code></pre>

<p>That one is added in the middle of a path.</p>

<p>I am wondering what the immutable data structure would be to handle these 2 situations. So essentially we have a function <code>f : graph -&gt; graph'</code> 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...</p>

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

<pre><code> --------------------------
|                          |
|    a -- b                |
|         |                |
|         c                |
|         |                |
|         d -- h           |
|              |           |
|         e -- i -- l      |
|              |           |
|         f -- j -- m      |
|              |           |
|         g -- k -- n      |
|                          |
 --------------------------
</code></pre>

<p>Then you make the change and it creates a <em>new</em> wrapper object.</p>

<pre><code> --------------------------           --------------------------
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------
</code></pre>

<p>Then likewise for the second example:</p>

<pre><code> --------------------------           -------------------------- 
|                          |         |                          |
|    a -- b                |         |                          |
|         |                |         |                          |
|         c                |         |                          |
|         |                |         |                          |
|         d -- h           |         |                          |
|              |           |         |                          |
|              o --------------------------------- x            |
|              |           |         |                          |
|         e -- i -- l      |         |                          |
|              |           |         |                          |
|         f -- j -- m      |         |                          |
|              |           |         |                          |
|         g -- k -- n      |         |                          |
|                          |         |                          |
 --------------------------           --------------------------
</code></pre>

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

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

<p>Thank you for your help.</p>
