cons 参数的不同规则？

Question

我是 Racket 语言的新手，遇到了一个问题。我现在正在尝试使用 cons(list) 实现二叉搜索树。

这是我尝试制作的简单 BST：

对于这个BST，如果我把它转换成Racket列表，这可能是一种可能性： '(6, (4, (), ()), (7, (), ())

为了生成这种格式的列表，我使用了以下代码：

(define x3 (cons 6 (cons (cons 4 (cons null (cons null null)))
                         (cons 7 (cons null (cons null null)))

对于这段代码，结果如下：

'(6 (4 () ()) 7 () ())

如您所见，这不是我想要的。第二个子节点 7 () () 不在括号内，这意味着它不作为列表存在。它充当单独的 3 个元素，而不是单个列表。所以我改了一点：

(define x2 (cons 6 (cons (cons (cons 4 (cons null (cons null null))) null)
                         (cons (cons 7 (cons null (cons null null))) null)
                   )
           )
)

对于第二个代码，结果如下：

'(6 ((4 () ())) (7 () ()))

这也不是我想要的。第一个子节点 ((4 () ())) 现在在列表内部。所以我做了最后的尝试，代码是这样的：

(define x3 (cons 6 (cons (cons 4 (cons null (cons null null)))
                         (cons (cons 7 (cons null (cons null null))) null)
                   )
           )
)

结果如下所示：

'(6 (4 () ()) (7 () ()))

现在可以了！问题是，为什么会发生这些事情？我有点意识到当使用 cons 时，列表的最后一个元素和另一个元素之间的规则是不同的，但毕竟，它们不是同一种列表吗？

Answer 1

当使用 cons 编写深层列表列表时，很容易忘记内部列表的开始位置或结束位置等。因此，如果您要写出很长的列表手动列出，简单地使用 list:

可能更容易

(list 6 (list 4 null null) (list 7 null null))

否则，您也可以通过从内向外书写来轻松构建 cons 列表。例如，在您的 BST 中，有两个叶节点和一个根父节点。所以可以从叶节点开始：

(define left   (cons 4 (cons null (cons null null))))
(define right  (cons 7 (cons null (cons null null))))

那么 BST 变成：

(cons 6
      (cons left
            (cons right null)))

相当于：

(cons 6
      (cons (cons 4 (cons null (cons null null)))
            (cons (cons 7 (cons null (cons null null))) null)))

Answer 2

首先：

cons 实际上创建了一个单元格，一个 cons 单元格。您可以使用 cons 将多个 cons 单元格相互附加。

(cons 'a 'b) ;; (a . b)
(cons 'c (cons 'a 'b)) ;; (c . (a . b))

lisp 表示法表示，' . ( ' 是 ' '，所以最后一个例子简化为：

(c a . b)

什么是列表？这样的 cons 单元或 cons 单元链，最后一个元素是 ' 。 ()'。在这种情况下，您可以使其不可见。

(cons 'c (cons 'a null)) ;; or 
(cons 'c (cons 'a 'null)) ;; or
(cons 'c (cons 'a '()))   ;; which are the same!
;; in common lisp even (cons 'c (cons 'a ())) in addition

因此简化为：

(c a) ;; actually (c . (a . null))

这些语法简化规则以及 cons 只接受 2 个参数但二叉树需要 3 个槽的事实，使得 cons 构造比问题看起来更复杂。

您的 BST 应表示为列表：

(list 6 (list 4 null null) (list 7 null null))

只用conses手动表达已经很复杂了... （如 assefamaru 所解释）

如您所见，list 是对 cons 嵌套的抽象，最内层的 cons - 单元格 cons 为 null，更适合语法的简化规则。因此对大脑更友好。

但更优雅的是，您应该通过定义每个节点都需要一个值以及一个左节点和一个右节点来使用结构（如此处解释https://learningtogetolder.wordpress.com/2013/08/14/creating-a-binary-search-tree-in-racket/）。因此，构造错误是不可能的。

cons 参数的不同规则？

Different rules for cons arguments?

list

cons

racket

binary-search-tree

data-structures