Idiomatic way to represent nullary data constructor

Question

In Haskell, if I wanted something like a binary tree I would use an algebraic data type.

data BinTree a b = EmptyBinTree | BinTree a (Maybe b) (BinTree a) (BinTree a)

In Common Lisp, I might represent an empty tree as a dedicated self-evaluating symbol like :empty-bin-tree or a general purpose one like nil. I would represent the general case of a binary tree as

(defun make-bin-tree
    (key-value
     &optional (left-child :empty-bin-tree)
     &optional (right-child :empty-bin-tree))
  "(list key value?) left-child? right-child? -> bin-tree"
  (list key-value left-child right-child))

With nothing explicit corresponding to the BinTree constructor in the Haskell code.

Is there an idiomatic or conventional way to represent the equivalent of a nullary data constructor as a self-evaluating symbol in the current package instead of re-purposing a keyword?

Answer 1

You can roll your own, as detailed in the other answer. It seems like you want to use ML-style algebraic data types in Common Lisp. It turns out you can: this amazing library by tarballs_are_good: https://github.com/stylewarning/cl-algebraic-data-type implements them.

Unfortunately, this library does not support parametric recursive types, because it is hard to retrofit these onto a dynamic language via macroology alone. If this abstraction is non-negotiable to you, you may want to look at a Lisp like Shen that supports it from the ground up.

Edit: trivia is now the de-facto standard for pattern matching libraries. It is compatible with optima but under more active development, I believe.

Answer 2

It's easy enough to make a symbol self-evaluating. You can just use defconstant. Then you can create a tree function like you're suggesting where the left and right subtrees are optional, and default to the empty tree:

(defconstant empty-tree 'empty-tree)

(defun tree (element &optional
                       (left empty-tree)
                       (right empty-tree))
  (list element left right))

CL-USER> (tree 3)
(3 EMPTY-TREE EMPTY-TREE)

CL-USER> (tree 3 (tree 4))
(3 (4 EMPTY-TREE EMPTY-TREE) EMPTY-TREE)

CL-USER> (tree 3 (tree 4) (tree 5))
(3 (4 EMPTY-TREE EMPTY-TREE) (5 EMPTY-TREE EMPTY-TREE))

That said, I don't know whether this would be considered particularly idiomatic. You now have a way to check for empty trees, but no definite way to check for non-empty trees. That is, how would you know whether it's a tree, or just some list?

I think that it would be more typical to use either completely implicit typing, or to use completely explicit typing. Implicit typing would say something like:

A binary tree is either:

• a list of the form (element left-subtree right-subtree)
• the empty tree, nil.

That's easy enough to implement:

(defun tree-element (tree)
  (first tree))

(defun tree-left (tree)
  (second tree))

(defun tree-right (tree)
  (third tree))

(defun treep (object)
  (and (listp object)
       (or (= 3 (length object))  ; doesn't check subtrees, though
           (null object))))

Note that the treep predicate doesn't check subtrees, though. That's kind of like listp, which will check whether something is nil or a cons, but doesn't go farther down. It's also a matter of taste whether the length of a tree really needs to be three or not. After all, you can still do, e.g., (tree-right '(1 (2))) and get nil back.

You could also do something a bit more explicit, with type information actually embedded into the objects, so that you could check arguments, etc. I think that's a less common approach, but you can get typed objects using CLOS or structures. Structures will, by default, give you a lot of the same accessors, too. An approach with structures might look like this (be sure to read the comments in the code):

(defstruct (binary-tree
             ;; By default, DEFSTRUCT would define a BINARY-TREE-P
             ;; predicate that would be true only of the structure
             ;; objects.  The structure objects are just the internal
             ;; nodes; NIL is the leaf, so instead we define
             ;; INTERNAL-BINARY-TREE-P, and define BINARY-TREE-P
             ;; later.
             (:predicate internal-binary-tree-p))
  element   ; defines binary-tree-element
  left      ;    ''   binary-tree-left
  right)    ;    ''   binary-tree-right

(defun binary-tree-p (object)
  (or (null object)
      (internal-binary-tree-p object)))

Or, you could a type hierarchy with structures, too. The problem with type hierarchies, of course, is that you have no way to lock them. E.g., you could define a binary-tree class with no slots, and then subclasses empty-binary-tree and internal-binary-tree, but if someone comes along and defines another subclass, it's a binary-tree, too, even though you wanted algebraic behavior.

Common Lisp is a flexible enough language that you can develop algebraic datatypes if you want, and forgiving enough that you can enforce as little or as much as you want. I think the most common approach, and certainly the easiest earlier on, would be to simply treat your data that way. The compiler won't enforce that you don't pass a non-tree to a tree-expecting function, but you can still get most of the benefits.