当前位置：文江博客话题详情

检查树之间相等性的函数

发布于 2024-10-06 17:24:49 字数 50 浏览 0 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

最丧也最甜 2024-10-13 17:24:49

从每棵树的根开始递归
如果根值相似 - 继续左子树，然后是右子树
任何差异 - 打破

回复收藏 0 原文

与他有关 2024-10-13 17:24:49

我们可以使用等于？

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

但是，为了一些乐趣，继 Vasserman 提到“中断”之后，这可能是利用计划连续控制能力的好机会！

如果我们发现树中存在任何差异，我们可以使用 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 让我们捕获当前的延续。我是这样调用这个过程的：

 (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

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

回复收藏 0 原文

浮世清欢 2024-10-13 17:24:49

我也得到了一个连续的答案。但现在我有两个延续，一个是真的，一个是假的。如果您想根据结果进行分支，这非常有用。我还添加了“相同？”，它隐藏了所有延续，因此您不必处理它们。

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

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

回复收藏 0 原文

~没有更多了~