Как я могу реализовать функцию равенства в схеме, которая берет 2 дерева и проверяет, имеют ли они одинаковые элементы и структуру?
Функция проверки равенства между деревьями
Ответы (3)
рекурсия от корня каждого из деревьев
если значения корня похожи - продолжить с левого поддерева, затем с правого поддерева
любая разница - разорвать
Мы могли бы использовать равно?
(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
call/cc
имеет к исходному вопросу? Похоже, вы просто хотели использовать CPS без всякой причины; это не сильно меняет фактический код. Тем не менее, вы никогда не (return #t)
поэтому #t
никогда не должны возвращаться.
- person configurator; 09.12.2010
У меня также есть продолжение-полный ответ. Но теперь у меня есть два продолжения: одно, если оно истинно, и одно, если оно ложно. Это полезно, если вы хотите перейти к результату. Я также включил '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)))))