트리 간의 평등을 검사하는 함수

Question

Scheme에서 2 개의 트리를 가져 와서 같은 요소와 구조를 모두 갖고 있는지 확인하는 equality 함수를 어떻게 구현할 수 있습니까?

Answer 1

나무
의 각 루트 값이 비슷한 경우 루트에서 재귀 - 왼쪽 서브 트리로 계속가, 마우스 오른쪽 서브 트리
차이가 -

가

Answer 2

우리는 동일한 를 사용할 수있는 휴식?

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

하지만, 재미를 들면, "휴식"의 Vassermans 언급에서에 다음이 전력을 제어하는 ​​구성표 계속 활용할 수있는 좋은 기회가 될 수도 있습니다!

우리는 나무가 다름을 알면 조기 반환을 위해 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))))) 

전화/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 

Answer 3

나는 또한 계속적인 답변을 얻었습니다. 그러나 지금은 두 개의 연속이 있습니다. 하나는 진리라면 하나는 거짓이라면 하나입니다. 결과에서 분기하려는 경우 유용합니다. 나는 또한 '동일?'을 포함 시켰습니다. 모든 연속체를 숨겨서 처리 할 필요가 없습니다.

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