How to 'mark' a node in a Clojure data structure?

Question

I have

• a Clojure data structure, let's call it dom, a tree of vectors and maps of indefinite depth;
• a particular node in it, let's call it the focus node, referred to as a path into the tree: a sequence of keys such as you could present to get-in.

I will be deciding on the focussed node in one function and I want to somehow represent that choice of focussed node in a way that can be passed to another function in a way that does not violate immutability and is not in conflict with Clojure's persistent data structures.

When I traverse the tree, I want to treat the focus node differently: for example, if I was printing the tree, I might want to print the focus node in bold.

If I were using C or Java, I could save a pointer/reference to the focus node, which I could compare with the current node as I traversed the tree. I don't think that's the right way to do it in Clojure: it feels hacky, and I'm sure there's some way to do it that takes advantage of Clojure's persistent data structures.

The solution has to work in Clojure and ClojureScript.

The options I can think of are:

1. Store a reference and check against that.
2. Attach a marker to the node in question.

3. Simultaneously recurse into the tree and along the path to the marked node.

   • Option (1) is unattractive, as I've explained.
   • Option (2) seems best, and painless given persistent data structures.
   • Option (3) is similar to option (2), except that it combines the marking and traversing steps.

I'm sure this is a common problem. Is there a standard solution to it?

Answer 1

I suggest you reconsider @MerceloMorales's suggestion: to use metadata. Your node object is to have an accidental attribute that doesn't affect its normal functions. That is what metadata is designed for. And it works in ClojureScript. The only reason I can think of for not using metadata is that the node value is not a Clojure object, but is, for example, a number.

In The Clojure Cookbook, 2.22. Keeping Multiple Values for a Key, Luke Vanderhart uses metadata to solve a similar problem: marking entries that need to be interpreted as collections rather than single values.

Another approach might be to use a zipper to traverse/modify the node tree. Zippers are implemented in terms of - you've guessed it - metadata.

I share your misgivings about metadata: it feels queasy to attach just any old stuff to your data - like infecting it with a parasite. However, it's just as immutable a part of the object as any other.

---

The suggestion to use zippers is naive: The standard clojure zippers are designed for a hierarchy of sequential containers, not associative ones.

Answer 2

See Brandon Bloom's Dendrology talk for some great overview on questions like this.

I believe the ease of "marking" or otherwise updating tree structured data underlies his strong recommendation to always represent nodes as nested maps rather than vectors (or a mixture of vectors and maps). A mark based on a path described by a vector of keys is then as simple as:

 (update-in tree-data path assoc :is-focussed true)

Your original data structure is unchanged and the new one returned by update-in shares everything structurally with the original except the updated node which is now easily tested for the :is-focussed property upon traversal.