如何检查Scheme中两个S表达式在结构上是否相同？

Question

我不完全确定如何解决这个问题。我想我想通过一个辅助函数单独通过x和y，并且帮助函数根据它找到的值返回一个值，然后在结构上比较它们（x？y）。但是，我可以想出使用这种方法可能出错的多种方法。

define (structurally? x y) 
(
... 
) 

例如：

(structurally? quote(1 2 (3 a 5) (b 6 c "string" 7 (5)) 9)  
       quote(2 1 (3 "string" 5) (b 6 c a 7 (5)) 9)) 

结果是#T

(structurally? '(1 2 (3 a b 5) (b 6 c "string" 7 (5)) 9) 
       '(2 1 (3 "string" 5) (b 6 c d a 7 (5)) 9)) 

结果是#F

Answer 1

为了达到这个目的，我们必须同时遍历两个列表，特别注意边缘情况。如果我们设法在没有其中一个结束的情况下遍历列表，那么我们可以说它们在结构上是平等的。试试这个：

(define (structurally? exp1 exp2) 
     ; if we reach the end of both lists, they're equal 
    (cond ((and (null? exp1) (null? exp2)) #t) 
     ; if we reach the end of one before the other, they're distinct 
     ((and (null? exp1) (not (null? exp2))) #f) 
     ; if we reach the end of one before the other, they're distinct 
     ((and (not (null? exp1)) (null? exp2)) #f) 
     ; if we find an atom they're equal, no matter its value 
     ((not (pair? exp1)) #t) 
     ; recursive step: advance over `car` and `cdr` of both lists 
     ; simultaneously, combining all partial results using `and` 
     (else 
     (and (structurally? (car exp1) (car exp2)) 
       (structurally? (cdr exp1) (cdr exp2)))))) 

它按预期工作：

(structurally? '(1 2 (3 a 5) (b 6 c "string" 7 (5)) 9) 
       '(2 1 (3 "string" 5) (b 6 c a 7 (5)) 9)) 
=> #t 

(structurally? '(1 2 (3 a b 5) (b 6 c "string" 7 (5)) 9) 
       '(2 1 (3 "string" 5) (b 6 c d a 7 (5)) 9)) 
=> #f 

Answer 2

我想我明白为什么你给的例子是真假，但我不确定结果表达式树的外观。假设您有表达式e，例如数学表达式(+ (+ 2 4) 5)。根，+是(car e)，左边的树，(+ 2 4)是(cadr e)，右边的树5是(caddr e)。在结构上，那表情是一样的(+ (- 3 7) 1)，但评估的结果是不同的...

如果您导航表达，并没有c(a)dr或c(a)ddr，你已经达到那个方向遍历结束。

您可能需要一个辅助方法，但我想象一下(and (equal? (car x) (car y)) (structurally? (cdr x) (cdr y)) (structurally? (cddr x) (cddr y)))的效果会让你开始。

Answer 3

奥斯卡·洛佩斯的解决方案能够以这种方式被简化：

(define (structurally? exp1 exp2) 
    (cond ((not (pair? exp1)) (not (pair? exp2))) 
      ((not (pair? exp2)) #f) 
      (else (and (structurally? (car exp1) (car exp2)) 
         (structurally? (cdr exp1) (cdr exp2)))))) 

在cond第一支我们说如果第一个表达式不是一对，那么函数的结果是检查第二个表达式是否不是一对的结果。这也是递归的最后一种情况，因为您无法在非对值上重复。

在第二个分支中，我们知道exp1是一对，所以如果exp2不是一对，则表达式在结构上不等效。这是递归的最后一种情况。

最后，递归情况等于另一个解决方案。