I've implemented a structural sharing algorithm for creating Clojure style persistent trees, but it relies on the child node knowing its own parent.

function fork
  return new Node
    children: this.children
    value: this.value
    parent: this.parent.fork()

Calling fork on a node in the tree will give you a new node, with a forked parent, recursively up until the root. This way you can take any node, change it and then have access to an immutable version of the whole tree.

However, the fundamental idea for this data structure is that it should be a directed acyclic graph, having a reference to a parent would give the graph cycles. I've also had some problems with creating the new parent. The node should know about the forked parent, but to fork the parent, it should know about its new child. This is pretty much a circular dependency, but I've managed to circumvent it with some references and mutation.

Is there a more sane way to do this?

  • 4
    Are you sure this kind of "cycle" is actually a problem? The implementation of a data structure is often more powerful than its interface - for instance, a stack is often implemented with an underlying array, even thouth the stack API doesn't allow random access. Are you afraid of violating the "spirit of the DAG", or of interfering with garbage collection? – Kilian Foth Sep 7 '15 at 13:59
  • Well it makes writing functional code pretty tricky, due to the circular reference dependencies. I don't mind the implementation being fundamentally different to the interface, but seeing as most of the reference material I can find on these algorithms mention DAGs, I wondered whether I was missing something. – Dan Prince Sep 7 '15 at 23:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.