How to "tag" a node in a Clojure data structure?

Question

I have

• a Clojure, let him call it dom , a tree of vectors and maps of indefinite depth;
• the specific node in it, let's call it focus node, called the path to the tree: a sequence of keys, for example, which you could imagine get-in .

I will solve a focused node in one function, and I want to somehow present this choice of a focused node in a way that can be passed to another function in such a way that it does not violate immutability and is not in conflict with stable Clojure data structures.

When I cross a tree, I want to relate to the focus node differently: for example, if I printed the tree, I could print the focus node in bold .

If I used C or Java, I could save a pointer / link to the focus node, which I could compare with the current node when I was crossing the tree. I don't think the right way to do this in Clojure is: it feels hacky, and I'm sure there is some way to do it that uses Clojure's robust data structures.

The solution should work in Clojure and ClojureScript.

Possible options:

• Save the link and check it.
• Attach a marker to node.

• At the same time, go to the tree and along the path to the marked node.

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

I am sure this is a common problem. Is there a standard solution?

Answer 1

I suggest you reconsider the @MerceloMorales proposal: use metadata. Your node object must have a random attribute that does not affect its normal functions. This is what metadata is for. And he works in ClojureScript. The only reason I can think about not using metadata is because the node value is not a Clojure object, but is, for example, a number.

In Clojure Cookbook, 2.22. By storing multiple values ​​for the key , Luke Vanderhart uses metadata to solve a similar problem: marking records that need to be interpreted as collections, rather than individual values.

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

I share your concerns about metadata: it feels sickening to attach only some old things to your data - for example, infect it with a parasite. However, it is as immutable as part of an object, like any other.

---

The proposal to use zippers is naive: standard Clojure zippers are designed for a hierarchy of consecutive containers, not associative ones.

Answer 2

See the Brandon Bloom Dendrology Discussion for a great overview on such issues.

I believe that the ease of “marking” or otherwise updating tree data is at the core of his strong recommendation to always represent nodes as nested maps, not vectors (or a mixture of vectors and maps). A sign based on the path described by the key vector is then simple as:

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

Your original data structure has not changed, and the new one returned by the update-in element has a structural structure with the original, except for the updated node, which is now easily tested for the property :is-focussed when :is-focussed .