用于表示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))

没有任何明确对应BinTree于Haskell代码中的构造函数.

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

Answer 1

您可以自己滚动,详见另一个答案.看起来你想在Common Lisp中使用ML风格的代数数据类型.事实证明你可以:tarballs_are_good这个神奇的图书馆:https://bitbucket.org/tarballs_are_good/cl-algebraic-data-type实现它们.

不幸的是,这个库不支持参数递归类型,因为仅通过宏观学很难将它们改进到动态语言上.如果这个抽象是不可协商的,你可能想看看像Shen一样从头开始支持它的Lisp .

如果你喜欢模式匹配很多,你可能想看看optima,一个用于常见Lisp的优化模式匹配器.cl-algebraic-data-typse确实有一个模式匹配宏,但目前没有实现嵌套模式匹配.我已经为optima编写了一个插件,允许它匹配cl-algebraic-data-types,你可以在这里找到:https://bitbucket.org/blevyq/adt-optima-bridge.不幸的是,它目前没有检查详尽无遗.

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

也就是说,我不知道这是否会被认为是特别惯用的.你现在有办法检查空树,但没有明确的方法来检查非空树.也就是说,你怎么知道它是树还是一些列表？

我认为使用完全隐式输入或使用完全显式输入更为典型.隐式打字会说:

二叉树是:

• 表单列表(元素left-subtree right-subtree)
• 空树,没有.

这很容易实现:

(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,它会检查某些东西是零还是缺点,但不会更进一步.树的长度是否确实需要为三,这也是一个品味问题.毕竟,你仍然可以做,例如, (树右'(1(2)))并且没有回来.

您也可以做一些更明确的事情,类型信息实际嵌入到对象中,以便您可以检查参数等.我认为这是一种不太常见的方法,但您可以使用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是一种足够灵活的语言,您可以根据需要开发代数数据类型,并且足够宽容以便您可以根据需要强制执行.我认为最常见的方法,当然也是最简单的方法,就是简单地以这种方式处理您的数据.编译器不会强制您不将非树传递给期望树的函数,但您仍然可以获得大部分好处.