:constructor tricks

Every once in a while I discover things in CL that somehow I had not thought about before. They have been there sometimes since CLtL1 but, somehow, I did not register them before. (I am slow, I know; and I am not claiming that this is anything new. But this is the Internet :) )

Fancy :constructor uses are one of these things.

Suppose you wanted to construct a immutable tree node structure which recorded the height of the sub-tree upon construction. Here is an iteration of what you may do.

(defstruct node
   (height 0)
   left
   right)

Now you need to create the constructor for nodes. Not worrying about nil nodes, you may start by doing the obvious (assuming a max* function capable of dealing with nil values):

(defun build-node (l r)
   (make-node :left l
              :right r
              :height (1+ (max* (node-height l) (node-height r)))))

Ok. Fine. But why having two constructors, with the standard make-node essentially useless (you would not want to advertise it, as height is a computed slot)?

However, you can do the following:

(defstruct (node
           (:constructor make-node (left right
                                    &aux
                                    (height (1+ (max* (node-height left) (node-height right))))))
   (height 0)
   left
   right)

This will work as expected; the key trick is to leverage the &aux parameter to collect the computation. Adding the appropriate :read-only declarations, you end up with:

(defstruct (node
           (:constructor make-node (left right
                                    &aux
                                    (height (1+ (max* (node-height left) (node-height right))))))
   (height  0 :read-only t :type (mod 42))
   (left  nil :read-only t :type (or null node))
   (right nil :read-only t :type (or null node))

A perfectly fine immutable node structure.

---

(cheers)