0
如何在需要2棵树并检查它们是否具有相同元素和结构的Scheme中实现相等函数？检查树之间的相等性的函数
A
回答
3
从根递归每个树
如果根值是相似的 - 继续与左子树，然后右子树
任何区别 - 打破
1
我们可以使用平等的吗？
(equal? '(a (b (c))) '(a (b (c))))
但是，对于一些乐趣，从“破发”的Vassermans提到以下时，这可能是采取计划延续的优势功率控制的好机会！
我们可以使用call/cc发出提前回报，如果我们注意到树中的任何差异。通过这种方式，我们可以跳回到呼叫者的继续而不必展开堆栈。
这是一个非常简单的例子。它假定树形成良好，只包含符号树叶，但它应该有希望展示这个概念。您会看到该过程明确接受延续作为参数。
(define (same? a b return)
(cond
((and (symbol? a) (symbol? b)) ; Both Symbols. Make sure they are the same.
(if (not (eq? a b))
(return #f)))
((and (empty? a) (empty? b))) ; Both are empty, so far so good.
((not (eq? (empty? a) (empty? b))) ; One tree is empty, must be different!
(return #f))
(else
(begin
(same? (car a) (car b) return) ; Lets keep on looking.
(same? (cdr a) (cdr b) return)))))
呼叫/立方厘米让我们抓住当前的延续。这里是我如何叫做这个程序：
(call/cc (lambda (k) (same? '(a (b)) '(a (b)) k))) ; --> #t
(call/cc (lambda (k) (same? '(a (b (c) (d e))) '(a (b (c) (d e))) k))) ; --> #t
(call/cc (lambda (k) (same? '(a (b (F) (d e))) '(a (b (c) (d e))) k))) ; --> #f
(call/cc (lambda (k) (same? '(a (b)) '(a (b (c) (d))) k))) ; --> #f
0
我也得到了一个持续的答案。但现在我有两个延续，一个如果是真的，另一个如果是假的。如果你想分析结果，这很有用。我还包括'相同'，它隐藏了所有的延续，所以你不必处理它们。
(define (same? a b)
(call/cc (λ (k) (cont-same? a b (λ() (k #t)) (λ() (k #f))))))
(define (cont-same? a b return-t return-f)
(define (atest c d)
;; Are they foo? If they both are, then true
;; If they both aren't false
;; if they are different, then we are done
(if (and c d)
#t
(if (or c d)
(return-f)
#f)))
(if (atest (null? a) (null? b)) ;; Are they both null, or both not null.
(return-t)
(if (atest (pair? a) (pair? b))
(cont-same? (car a)
(car b)
(λ() (cont-same? (cdr a) (cdr b) ;; If the head are the same, compare the tails
return-t return-f)) ;; and if the tails are the same, then the entire thing is the same
return-f)
(if (equal? a b) ;; Both are atoms
(return-t)
(return-f)))))
让我们仔细想一想。如果我们有两棵树，每棵树都有一个元素，我们如何判断它们是否相等？ – 2010-12-08 03:50:55
长度相等（因为它们是由列表表示的），还是“eq？”也许？ – pantelis4343 2010-12-08 03:55:42
你仍然试图直接跳到整个解决方案。这不是正确的方式 - 你想解决最小的问题，然后建立一个更大的解决方案。因此，如果我们有一棵*一个元素*（它只包含根节点），并且我们有另一个*一个元素*的树，我们将如何检查它们是否相同？ – 2010-12-08 03:58:38