recursion - 如何在 Lisp/scheme 中递归地编写 adjoin-set

Question

我想写下面的例子:

(adjoin-set 2 (adjoin-set 8 (adjoin-set 4 (adjoin-set 3 (adjoin-set 7 (adjoin-set 5 '()))))))

递归地。

我的其他代码如下(来自Structure and Interpretation of Computer Programs, 2nd ed.)

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))


(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

到目前为止，我已经尝试了以下方法:

(define (bst list)
  (if (null? list) '())

  (bst (adjoin-set (cdr list) '())))

这行不通。我怎样才能做到这一点？

我想采用与手动调用时类似的方法，即 (adjoin-set (car list) (next adjoint-set))。

Answer 1

首先，我不使用二叉搜索树来表示集合，而是使用没有重复元素的列表。重点是我们将编写一个方法来连接一个单个 元素，然后弄清楚如何用多个值重复调用它并获得最终结果。您仍然可以将此方法应用于基于树的实现。

用不包含重复项的列表表示集合

如果我们用没有重复的列表表示集合，那么单个 adjoin 只需要一个元素和一个列表，如果元素已经在列表中，则返回列表，或者从创建的新列表新元素和旧列表，如果列表不包含它。所以，adjoin 并不太难:

(define (member? element list)
  (cond
    ((null? list) #f)
    ((eqv? (car list) element) #t)
    (else (member? element (cdr list)))))

(define (adjoin element set)
  (if (member? element set)
      set
      (cons element set)))

这与您已经通过 SICP 的adjoin-set 获得的内容相对应。

执行多个操作

现在，如果您希望能够将一堆元素连接到某个初始值，您将执行缩减，或折叠。 reduce 或 fold(以及 foldr、foldl 等)有很多变体实现，但是快速简单的左关联版本是:

(define (reduce function list initial-value)
  (if (null? list)
      initial-value
      (reduce function
              (cdr list)
              (function (car list) initial-value))))

现在，您可以减少您的 adjoin 函数在 的元素列表上并获得最终结果:

(define (adjoin* elements set)
  (reduce adjoin elements set))

这里有两个例子，将一堆元素连接到一些预先存在的集合。在第一种情况下，集合是空集。在第二种情况下，它是集合 (1 2 3 4)。当然，要使其与您的代码一起使用，这些初始集需要是基于树的集。

(display (adjoin* '(5 7 3 4 8 2) '()))
;;=> (2 8 4 3 7 5)

(display (adjoin* '(5 7 3 4 8 2) '(1 2 3 4)))
;;=> (8 7 5 1 2 3 4)