Idiomatic way to represent nullary data constructor

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 b) (BinTree a b)

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?

Solution

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.