Pointer cycles in clojure

Question

I'm writing a clojure program which parses XML. As a part of this, I wish to create a tree of the nodes in the XML document, based on the clojure.xml/parse function. However I'd like the tree to be bi-directional - that is, each node has a list of children, and a pointer to its parent. There is only one problem: all data is immutable, and so I can't 'add' a pointer to the parent without changing the child, thus making the parent's pointer useless.

I've found this answer: How can one create cyclic (and immutable) data structures in Clojure without extra indirection?

The solution suggested there seems to be creating a separate index map, which refers to the objects inside. This seems like a huge amount of work for a much worse solution. I'd have no problem for the tree to be mutable during construction, however I can't figure out how can it be done. Is there really no way to get a cyclic pointer in clojure?

Thanks!

Answer 1

It's logically impossible to make pure immutable structures cyclic, since by adding a parent or child pointer you would be mutating the structure.

There is a hack that works though I'm not sure I'd recommend it: you can put atoms inside Clojure data structures and then mutate these to make the necessary links. e.g.

(def parent {:id 1 :children (atom nil) :parent (atom nil)})

(def child  {:id 2 :children (atom nil) :parent (atom nil)}) 

(swap! (:children parent) conj child)
(reset! (:parent child) parent)

;; test it works
(:id @(:parent child))
=> 1

This is nasty in all sorts of ways:

• It will cause your REPL to stack overflow if you try and print one of these because the REPL isn't expecting cyclic data structures.
• It is mutable, so you lose all the maintainability and concurrency benefits of immutable data structures (which is one of the nicest things about Clojure!)
• You'll need to take a full copy of a node if you want to duplicate it (e.g. building a new XML document), since it isn't an immutable value any more.
• Dereferencing all the atoms can get messy as you navigate the structure.
• You'll confuse people who are used to idiomatic Clojure.

So, it is possible if you really want to do it......... though I personally think you are still much better off in the long run if you make your document representation properly immutable. You could perhaps use something more like XPath style locations in the document if you want to navigate the structure.

Answer 2

Have you considered using zippers?

Zippers are designed for allowing for working with tree like structures effectively. It includes basic operations like looking at children and at the parent of a node while also allowing easily iterating through the structure.

Zippers are fairly generic and included functions already allow creating them from XML. An example on the Other Libraries page offers a good initial picture of how to work with them.

For an XML zipper, you'll want to use

(clojure.zip/xml-zip (clojure.xml/parse file))

to create the initial structure. When you're done, just call root to get the end structure.