社区首页 >问答首页 >函数检查树之间的相等性。

问函数检查树之间的相等性。
EN

Stack Overflow用户

提问于 2010-12-08 03:48:20

回答 3查看 920关注 0票数 0

如何在Scheme中实现一个相等函数，以获取2个树并检查它们是否具有相同的元素和结构？

scheme

equality

tree

回答 3

Stack Overflow用户

发布于 2010-12-08 03:56:17

从每个树的根开始递归

如果根值相似-继续使用左子树，然后使用右子树

任何差异-中断

票数 3

Stack Overflow用户

发布于 2010-12-08 23:50:07

我们可以使用等于？

 (equal? '(a (b (c))) '(a (b (c))))

但是，有趣的是，在Vasserman提到“中断”之后，这可能是一个利用方案继续控制功率的好机会！

如果我们注意到树中的任何差异，我们可以使用调用/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)))))

调用/cc让我们捕获当前的延续。下面是我调用此过程的方式：

 (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

票数 1

Stack Overflow用户

发布于 2010-12-09 01:51:19

我也得到了一个连续的答案。但是现在我有两个延续，一个是真的，另一个是假的。如果你想在结果上进行分支，这是很有用的。我还包含了'same？‘，它隐藏了所有的延续，这样你就不必处理它们了。

(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)))))