计划等树程序

Question

在 Scheme 中使用列表实现树的新实现：

(define make-tree list)
(define add-subtree cons)
(define make-leaf (lambda (x) x))
(define empty-tree? empty?)
(define first-subtree car)
(define rest-tree cdr)
(define composite-tree? list?)
(define leaf? (lambda (x) (not (composite-tree? x))))

实施 CPS 过程 equal-tree$ 接收一对叶值树，t1 和 t2，以及两个延续：succ 和 fail并确定它们的结构标识如下：

if t1 和 t2 具有相同的结构，equal-tree$ returns 一棵具有相同结构的树，但每个叶子包含一对在这个位置加上原来两棵树的叶子（不管它们的值是否一致）。
否则，equal-tree$returns一对与深度优先遍历树中第一个冲突的子树。

例如：

(define id (lambda (x) x))
(equal-trees$ '(1 (2) (3 9)) '(7 (2) (3 5)) id id) ---> '((1 . 7) ((2 . 2)) ((3 . 3) (9 . 5)))

我尽力解决了这个问题，但我遇到了一个错误，希望有人能帮助我修复它。

这是我的尝试：

(define equal-tree$
  (lambda (tree1 tree2 succ fail)
    (if (and (empty? tree1) (empty? tree2))
      '()
      (if (or (empty? tree1) (empty? tree2))
        (fail '())
        (if (and (leaf? tree1) (leaf? tree2))
          (succ (cons tree1 tree2))
          (if (or (leaf? tree1) (leaf? tree2))
            (fail (cons (car tree1) (car tree2)))
            (equal-tree$ (car tree1) (car tree2) 
               (lambda (X) cons(cons (car tree1) (car tree2)) x) fail)))))
   )
)

这是上面示例的输出（我只是不知道为什么它打印 '(1 . 7) ... :

'(1 . 7)

Answer 1

你有一个看起来合理的 if 测试序列（尽管使用 cond 会更惯用 Scheme）。但是您 return 的值通常看起来不正确。

我看到的第一个问题是在您的第一个 if 子句中。如果两棵树都是空的，你 return '()。但是根据规范，您应该使用该结果调用 succ 函数。如果您使用 id 作为延续，这可能看起来并不重要，但请注意，每个递归步骤都会构建更详细的 succ 延续，因此通常 succ 可能是一个非常有影响力的函数。

第二个if也是一个问题。当您应该 return 第一个冲突的子树时，您再次 return '()。我不清楚这意味着什么，但是将一对 tree1 和 tree2 传递给 fail.

是合理的

第三条和第四条看起来不错。正如预期的那样，您用两片叶子中的一对调用 succ。

递归调用显然是错误的：您对 cons 的括号调用错误，并且您的 lambda 变量名为 X 但您将其称为 x。 cons 调用系列看起来也不太正确，但您可以在更紧迫的语法问题得到解决并且基本案例正常工作后进行试验。

最后，您正在使用 cons、car、'() 等进行大量低级工作。您应该使用提供给您的抽象函数，例如 add-subtree 和 (make-tree)，而不是使用它们所基于的低级原语。

计划等树程序

Scheme equal-tree procedure

tree

scheme

continuation-passing

racket