Fonction de vérification de l'égalité entre les arbres

Question

Comment puis-je implémenter une fonction d'égalité dans Scheme qui prend 2 arbres et vérifie s'ils ont à la fois les mêmes éléments et la même structure?

Answer 1

récursion de la racine chacun des arbres
si les valeurs de racines sont semblables - continuer avec la sous-arborescence à gauche, puis sous-arbre droit
toute différence - break

Answer 2

Nous pourrions utiliser égaux?

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

Mais, pour l'amusement, à la suite de la mention Vassermans d'une « rupture », cela pourrait être une bonne occasion de profiter de la poursuite des systèmes de contrôle de puissance!

Nous pouvons utiliser appel/cc pour émettre un retour anticipé si nous remarquons une différence dans les arbres. De cette façon, nous pouvons simplement revenir à la poursuite des appelants sans avoir à dérouler la pile.

Voici un exemple très simple. Il suppose que les arbres sont bien formés et ne contiennent que des symboles en guise de feuilles, mais il est souhaitable que le concept soit démontré. Vous verrez que la procédure accepte explicitement la continuation en tant que paramètre.

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

appel/cc nous permet de capturer la poursuite actuelle. Voici comment j'ai appelé cette procédure:

(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

J'ai aussi une réponse continue. Mais maintenant j'ai deux suites, une si elle est vraie, et une si elle est fausse. Ceci est utile si vous voulez ramifier le résultat. J'ai aussi inclus 'same ?, qui cache toutes les suites afin que vous n'ayez pas à les traiter.

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