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

Question

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

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

在 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

构造函数明确对应的内容。

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

Answer 1

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

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

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

Answer 2

使符号自我评估很容易。 你可以只使用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)))

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

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