---
# System prepended metadata

title: the little schemer - `eqlist?`詳解
tags: [scheme]

---

# 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?`

```scheme=
(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)`可簡化如下：

```scheme=
(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。
```scheme=
(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?`可簡化為
```scheme=
(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 |