In Clojure, when should trees of heterogenous node types be represented using records or vectors?

6
votes

Which is better idiomatic clojure practice for representing a tree made up of different node types:

A. building trees out of several different types of records, that one defines using deftype or defrecord:

(defrecord node_a [left right])
(defrecord node_b [left right])
(defrecord leaf [])

(def my-tree (node_a. (node_b. (leaf.) (leaf.)) (leaf.)))

B. building trees out of vectors, with keywords designating the types:

(def my-tree [:node-a [:node-b :leaf :leaf] :leaf])

Most clojure code that I see seems to favor the usage of the general purpose data structures (vectors, maps, etc.), rather than datatypes or records. Hiccup, to take one example, represents html very nicely using the vector + keyword approach.

When should we prefer one style over the other?

2
clojuretreetypesidioms
I hope that the question isn't too vague. I formulated it this way, because this sort of decision, to use records or the generic data structures seems to come up fairly often, and the answer often isn't obvious. To me, at least. – Rob Lachlan
It largely depends on what you expect to be doing with the nodes. For what it's worth, it might be useful to have nodes that can work with the clojure.zip zipper library. – Alex Taggart

2 Answers

3
votes

You can put as many elements into a vector as you want. A record has a set number of fields. If you want to constrain your nodes to only have N sub-nodes, records might be good, e.g. making when a binary tree, where a node has to have only a Left and Right. But for something like HTML or XML, you probably want to support arbitrary numbers of sub-nodes.

Using vectors and keywords means that "extending" the set of supported node types is as simple as putting a new keyword into the vector. [:frob "foo"] is OK in Hiccup even if its author never heard of frobbing. Using records, you'd potentially have to define a new record for every node type. But then you get the benefit of catching typos and verifying subnodes. [:strnog "some bold text?"] isn't going to be caught by Hiccup, but (Strnog. "foo") would be a compile-time error.

Vectors being one of Clojure's basic data types, you can use Clojure's built-in functions to manipulate them. Want to extend your tree? Just conj onto it, or update-in, or whatever. You can build up your tree incrementally this way. With records, you're probably stuck with constructor calls, or else you have to write a ton of wrapper functions for the constructors.

Seems like this partly boils down to an argument of dynamic vs. static. Personally, I would go the dynamic (vector + keyword) route unless there was a specific need for the benefits of using records. It's probably easier to code that way, and it's more flexible for the user, at the cost of being easier for the user to end up making a mess. But Clojure users are likely used to having to handle dangerous weapons on a regular basis. Clojure being largely a dynamic language, staying dynamic is often the right thing to do.

3
votes

This is a good question. I think both are appropriate for different kinds of problems. Nested vectors are a good solution if each node can contain a variable set of information - in particular templating systems are going to work well. Records are a good solution for a smallish number of fixed node types where nesting is far more constrained.

We do a lot of work with heterogeneous trees of records. Each node represents one of a handful of well-known types, each with a different set of known fixed keys. The reason records are better in this case is that you can pick the data out of the node by key which is O(1) (really a Java method call which is very fast), not O(n) (where you have to look through the node contents) and also generally easier to access.

Records in 1.2 are imho not quite "finished" but it's pretty easy to build that stuff yourself. We have a defrecord2 that adds constructor functions (new-foo), field validation, print support, pprint support, tree walk/edit support via zippers, etc.

An example of where we use this is to represent ASTs or execution plans where nodes might be things like Join, Sort, etc.

Vectors are going to be better for creating stuff like strings where an arbitrary number of things can be put in each node. If you can stuff 1+ <p>s inside a <div>, then you can't create a record that contains a :p field - that just doesn't make any sense. That's a case where vectors are far more flexible and idiomatic.