如何檢查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不是一對，則表達式在結構上不等效。這是遞歸的最後一種情況。

最後，遞歸情況等於另一個解決方案。