# the little schemer - `eqlist?`詳解
###### tags: `scheme`
# `eqlist?`定義

判斷`l1`, `l2`這 2 個 list 是否相同。

已知這 2 個 list 可能的情形有 3×3=9 種：

| `(eqlist? l1 l2)` | 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
| --- | --- | --- | --- |
| 結果`B1`：(null? `l2`)| `true` | `false` | `false` |
| 結果`B2`：(atom? (car `l2`) | `false` | ? | `false`|
| 結果`B3`：(eqlist? (car `l2`)) | `false`| `false`|?|

為方便接下來的說明，將以上 9 種結果設定名稱如下：

| result| 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
| --- | --- | --- | --- |
| 結果`B1`：(null? `l2`) | `A1B1` | `A2B1` | `A3B1` |
| 結果`B2`：(atom? (car `l2`)| `A1B2` | `A2B2` | `A3B2` |
| 結果`B3`：(eqlist? (car `l2`)) | `A1B3`| `A2B3` | `A3B3` |

# 以`eqan?`寫`eqlist?`

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((and (null? l1) (atom? (car l2))) #f)
      ((null? l1) #f)
      ((and (atom? (car l1)) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
        (and (eqan? (car l1) (car l2))
             (eqlist? (cdr l1) (cdr l2))))
      ((atom? (car l1)) #f)
      ((null? l2) #f)
      ((atom? (car l2)) #f)
      (else (and (eqlist? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

| line | meaning | result |
| ---- | -------------------- | ------ |
| 4 | `A1B1` | `A1B1` |
| 5 | `A1B2` | `A1B2` |
| 6 | `A1`-(`A1B1`+`A1B2`) | `A1B3` |
| 7 | `A2B1` | `A2B1` |
| 8 | `A2B2` | `A2B2` |
| 11 | `A2`-(`A2B1`+`A2B2`) | `A2B3` |
| 12 | `B1`-(`A1B1`+`A2B1`) | `A3B1` |
| 13 | `B2`-(`A1B2`+`A3B2`) | `A3B2` |
| 14 | `else` | `A3B3` |

## 以`or`簡化

為方便接下來的說明，將`or`相關結果設定名稱如下：

- `(or (null? l1) (null? l2))` = `A1orB1`
- `(or (atom? (car l1)) (atom? (car l2)))` = `A2orB2`

`A1orB1`=`A1B1`+`A1B2`+`A1B3`+`A2B1`+`A3B1`：
| ==`A1orB1`== | 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
|--- | --- | --- | --- |
| 結果`B1`：(null? `l2`) | ==`true`== | ==`false`== | ==`false`== |
| 結果`B2`：(atom? (car `l2`) | ==`false`== | ? | `false` |
| 結果`B3`：(eqlist? (car `l2`)) | ==`false`== | `false` | ? |

注意`A1B1`與`A1orB1`的其他結果不同。

`A2orB2`=`A2B1`+`A2B2`+`A2B3`+`A1B2`+`A3B2`

| ==`A2orB2`== | 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
| --- | --- | --- | --- |
| 結果`B1`：(null? `l2`) | `true` | ==`false`== | `false` |
| 結果`B2`：(atom? (car `l2`)| ==`false`== | ==?== | ==`false`==|
| 結果`B3`：(eqlist? (car `l2`)) | `false`| ==`false`==|?|

注意`A2B2`與`A2orB2`的其他結果不同。

因此，`(eqlist? l1 l2)`可簡化如下：

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      ((and (atom? (car l1)) (atom? (car l2)))
        (and (eqan? (car l1) (car l2))
             (eqlist? (cdr l1) (cdr l2))))
      ((or (atom? (car l1)) (atom? (car l2))) #f)
      (else (and (eqlist? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

| line | meaning | result|
| --- | --- | --- |
| 4 | `A1B1` | `A1B1` |
| 5 | `A1orB1`-`A1B1` | `A1B2`+`A1B3`+`A2B1`+`A3B1` |
| 6 | `A2B2` | `A2B2` |
| 9 | `A2orB2`-`A2B2`-(`A1B2`+`A2B1`) | `A2B3`+`A3B2` |
| 10 | `else` | `A3B3` |

| line | 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
| --- | --- | --- | --- |
| 結果`B1`：(null? `l2`)| 4 | 5 | 5 |
| 結果`B2`：(atom? (car `l2`)| 5 | 6 | 9 |
| 結果`B3`：(eqlist? (car `l2`))| 5 | 9 | 10 |
# 以`equal?`寫`eqlist?`
`equal?`可判斷2個S-expression是否相同。
S-expression為atom或（空白的）list。

(define equal?
  (lambda (s1 s2)
    (cond
      ((and (atom? s1) (atom? s2))
        (eqan? s1 s2))
      ((or (atom? s1) (atom? s2))
        #f)
      (else (eqlist? s1 s2)))))

`equal?`描述4種結果：`A2B2`+`A2B3`+`A3B2`+`A3B3`。
因此`eqlist?`可簡化為

(define eqlist?
  (lambda (l1 l2)
    (cond
      ((and (null? l1) (null? l2)) #t)
      ((or (null? l1) (null? l2)) #f)
      (else (and (equal? (car l1) (car l2))
                 (eqlist? (cdr l1) (cdr l2)))))))

| line | 結果`A1`：(null? `l1`) | 結果`A2`：(atom? (car `l1`)) | 結果`A3`：(eqlist? (car `l1`)) |
| --- | --- | --- | --- |
| 結果`B1`：(null? `l2`)| 4 | 5 | 5 |
| 結果`B2`：(atom? (car `l2`)| 5 | 6 | 6 |
| 結果`B3`：(eqlist? (car `l2`))| 5 | 6 | 6 |