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

Question

我不太确定如何处理这个问题。我想我想用一个辅助函数分别遍历 x 和 y，并让那个辅助函数 return 一个值取决于它找到什么，然后在（结构上？ 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

我想我明白为什么你给出的例子是真假，但我不确定结果表达式树是什么样的。假设您有表达式 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 2

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

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

Óscar López 的解可以这样简化：

(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 不是一对，则表达式在结构上不等价。这是递归的另一个最终情况。

最终，递归情况等于另一种解法。

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

How to check whether two S-expressions are structurally identical in Scheme?

scheme

racket