Function to check equality between trees

How can I implement an equality function in Scheme that takes 2 trees a开发者_如何学JAVAnd checks if they have both the same elements and structure?

recursion from the root each of the trees
if the root values are similar - continue with the left subtree, then right subtree
any difference - break

We could use equal?

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

But, for some fun, following on from Vassermans mention of a "break", this might be a good chance to take advantage of Schemes continuation controlling power!

We can use call/cc to issue an early return if we notice any difference in the trees. This way we can just jump back to the callers continuation without having to unwind the stack.

Here is a really simple example. It assumes the trees are well-formed and only contain symbols as leaves, but it should hopefully demonstrate the concept. You'll see that the procedure explicitly accepts the continuation as a parameter.

 (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 lets us capture the current continuation. Here is how I called this procedure:

 (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

I've also got a continuation-ful answer. But now I have two continuations, one if it is true, and one if it is false. This is useful if you want to branch on the result. I've also included 'same?, which hides all the continuations so you don't have to deal with them.

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