title: How do I manipulate a tree of immutable objects?
body: <p>I'm building an entire application out of immutable objects so that multi-threading and undo become easier to implement. I'm using the <a href="http://code.google.com/p/google-collections/" rel="noreferrer">Google Collections Library</a> which provides immutable versions of Map, List, and Set.</p>
  
  <p>My application model looks like a tree:</p>
  
  <ul>
  <li>Scene is a top-level object that contains a reference to a root Node.</li>
  <li>Each Node can contain child Nodes and Ports.</li>
  </ul>
  
  <p>An object graph might look like this:</p>
  
  <pre><code>Scene
   |
   +-- Node
        |
        +-- Node 
             |
             +- Port
        +-- Node
             |
             +- Port
             +- Port
  </code></pre>
  
  <p>If all of these objects are immutable, controlled by a top-level SceneController object:</p>
  
  <ul>
  <li>What is the best way to construct this hierarchy?</li>
  <li>How would I replace an object that is arbitrarily deep in the object tree?</li>
  <li>Is there a way to support back-links, e.g. a Node having a "parent" attribute?</li>
  </ul>
  
  <p>And more generally:</p>
  
  <ul>
  <li>Have any patterns emerged for dealing with this type of data? </li>
  <li>Is there (academic) literature available on the subject?</li>
  <li>Is this a good idea?</li>
  </ul>