title: Immutable data structure for a DAG?
body: <p>I am looking for an immutable alternative to a data structure I saw used in a mutable program. (Seen in <a href="http://fmv.jku.at/papers/Biere-JSAT08.pdf" rel="nofollow noreferrer">this article</a>, figure 4). It is a DAG where each node has two pointers. The rationale is we have multiple sets, and each element is part of two of the sets, with a link to its successor in each set. Thus the structure allows us to traverse along the elements of each set like we had a linked list for each one of them.</p>
  
  <p><a href="https://i.stack.imgur.com/4G6Up.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4G6Up.png" alt="Exotic two-watched literals data structure"></a></p>
  
  <p>Linked lists are kind of popular in the functional and immutable world, but a doubly linked list offers great implementation challenges. It is said you can implement them with laziness, at least in some languages, but if a Scala programmer has a sequence where elements will be often removed or inserted in the middle, then you're probably just better off with a <code>Vector</code>.</p>
  
  <p>To remove an element from this data structure using mutability, you just need to locate the two predecessors of an element, and replace their successors for the respective successor-successors.</p>
  
  <p>Doing that in an immutable singly linked list forces us to rebuild all the predecessors, a price we might decide to pay, or to use <code>Stream</code> to remove the element lazily. But for this data structure here, we would now have to rebuild the two predecessors from the node, for both sets it belongs to, plus all its predecessors predecessors in all their sets!</p>
  
  <p>I found this a quite interesting example of a data structure that poses great challenges for immutable design, and I am curious to find out now: what would be a good functional, immutable persistent way to implement this data structure? A similar challenge is probably faced in the design of a data structure for sparse matrices (as seen in <a href="https://en.wikipedia.org/wiki/Dancing_Links" rel="nofollow noreferrer">DLX</a>).</p>
  
  <p>The best I could come up with so far is to just go for an adjacency list stored in a <code>Map[Node,(Node,Node)]</code>. Would this be the best approach for this problem, sticking to immutability? Or could we turn this weird DAG-list into a tree, perhaps?... I often hear finger trees can solve anything, is there a remote chance we might use them in this case?</p>