如何用CL表达树？

Question

我想将以下 OCaml 类型（不平衡二叉树）转换为 Common Lisp，但作为 CL 新手，我不知道如何使用动态语言来实现。

type 'a tree =
    Leaf
  | Node of 'a * 'a tree * 'a tree

如有任何建议，我们将不胜感激！

Answer 1

标准的缺点是你的树节点，car是左子树，cdr是右子树。

请参阅 http://nostoc.stanford.edu/jeff/llisp/13.html（现在位于 archive.org） 了解更多信息。

Answer 2

Base Common Lisp 没有可区分的联合类型定义。

我发现使用 CLOS 取得了一定的成功：

(defclass tree () (data left right))  

有关使用 DEFCLASS 的更多信息，请参阅 http://www.gigamonkeys.com/book/object-reorientation-classes.html。

更节省内存的方法是使用 DEFSTRUCT 而不是 DEFCLASS。