Функция для проверки равенства между деревьями - PullRequest
Новая
       22

Функция для проверки равенства между деревьями

0 голосов
/ 08 декабря 2010

Как я могу реализовать функцию равенства в Scheme, которая берет 2 дерева и проверяет, имеют ли они одинаковые элементы и структуру?

Ответы [ 3 ]

3 голосов
/ 08 декабря 2010

рекурсия от корня каждого из деревьев
если корневые значения похожи - продолжайте с левого поддерева, затем правого поддерева
любая разница - перерыв

1 голос
/ 09 декабря 2010

Мы могли бы использовать равно? 

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

Но, для некоторого веселья, после упоминания Вассерманом о "перерыве", это может быть хорошим шансом воспользоваться преимуществами продолжения Схем, управляющими силой!

Мы можем использовать 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
0 голосов
/ 09 декабря 2010

У меня также есть полный ответ.Но теперь у меня есть два продолжения: одно, если это правда, и одно, если это неверно.Это полезно, если вы хотите перейти на результат.Я также включил «то же самое?», Которое скрывает все продолжения, поэтому вам не нужно иметь с ними дело. 

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