表示 nullary 数据构造函数的惯用方式

Question

在 Haskell 中，如果我想要二叉树之类的东西，我会使用代数数据类型。

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

在 Common Lisp 中，我可能将一棵空树表示为专用的自评估符号，如 :empty-bin-tree 或通用符号，如 nil。我会将二叉树的一般情况表示为

(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))

Haskell 代码中没有明确对应于 BinTree 构造函数。

是否有一种惯用的或传统的方式来将 nullary 数据构造函数的等价物表示为当前包中的自评估符号，而不是重新使用关键字？

Answer 1

让一个符号自我评估是很容易的。你可以只使用 defconstant。然后你可以像你建议的那样创建一个树函数，其中左右子树是可选的，默认为空树：

(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))

也就是说，我不知道这是否会被认为是特别惯用的。您现在有一种检查空树的方法，但没有确定的方法来检查非空树。也就是说，您如何知道它是一棵树还是一些列表？

我认为使用完全隐式类型或使用完全显式类型会更典型。隐式输入会说这样的话：

二叉树是：

形式列表（元素左子树右子树）
空树，无。

这很容易实现：

(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))))

请注意，treep 谓词不检查子树。这有点像 listp，它会检查某些东西是 nil 还是 cons，但不会不要再往下走。树的长度是否真的需要为三也是一个品味问题。毕竟，您仍然可以执行 (tree-right '(1 (2))) 并返回 nil。

您还可以做一些更明确的事情，将类型信息实际嵌入到对象中，以便您可以检查参数等。我认为这是一种不太常见的方法，但您可以使用 CLOS 或结构。默认情况下，结构也会为您提供许多相同的访问器。使用结构的方法可能如下所示（请务必阅读代码中的注释）：

(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)))

或者，您也可以使用具有结构的类型层次结构。当然，类型层次结构的问题是您无法锁定它们。例如，您可以定义一个没有槽的二叉树 class，然后子 class 是空二叉树和内部二叉树，但是如果有人来定义另一个子 class，它也是一个二叉树，即使你想要代数行为。

Common Lisp 是一种足够灵活的语言，您可以根据需要开发代数数据类型，并且足够宽容，您可以随心所欲地强制执行。我认为最常见的方法，当然也是早期最简单的方法，就是简单地以这种方式处理您的数据。编译器不会强制您不将非树传递给期望树的函数，但您仍然可以获得大部分好处。

Answer 2

您可以自己滚动，如其他答案中所述。看起来您想在 Common Lisp 中使用 ML 风格的代数数据类型。事实证明你可以：tarballs_are_good 这个令人惊叹的库：https://github.com/stylewarning/cl-algebraic-data-type 实现了它们。

不幸的是，这个库不支持参数递归类型，因为仅通过宏观学很难将它们改造成动态语言。如果这种抽象对你来说是不可协商的，你可能想看看像 Shen 这样从头开始支持它的 Lisp。

编辑：trivia 现在是模式匹配库的实际标准。我相信它与 optima 兼容，但在更积极的开发中。

表示 nullary 数据构造函数的惯用方式

Idiomatic way to represent nullary data constructor

common-lisp