Scheme手習い (7) 一般のリストの再帰（続き）

第5章「*すごい*星がいっぱいだ」の続きです

指定したアトムが木に現れる回数を数えるoccur*、指定したアトムを置き換えるsubst*、
指定したアトムの左にアトムを挿入するinsertL*を作ります
前回みっちり考えたのでここらへんは楽勝
数を作ったりリストを作ったり

次は真偽を作ります
指定したアトムが含まれるかどうかを判定するmember*はこう

(define member*
  (lambda (a l)
    (cond ((null? l) #f)
          ((atom? (car l)) (or (eq? (car l) a) (member* a (cdr l))))
          (else (or (member* a (car l)) (member* a (cdr l)))))))

consや+の代わりにorを使っています
andを使うこともあるでしょうね

aが chips、lが((potato) (chips ((with) fish) (chips))))のとき、

どのchipsを見つけましたか。

schemeでは、引数をどういう順に評価するかは決まっていませんが
orは特殊形式で左から評価することが決まっていてcdrよりもcarを先に探します
だから左のchipsを見つけるはず

確かめ
(or A B) = (cond (A #t) (else B))なので
(or #t B)はBを評価しないですぐ#tに、(or #f B)はBに置き換えます

(member* 'chips '((potato) (chips ((with) fish) (chips))))
(or (member* 'chips '(potato)) (member* 'chips '((chips ((with) fish) (chips)))))
(or (or (eq? 'chips 'potato) (member* 'chips '())) (member* 'chips '((chips ((with) fish) (chips)))))
(or (or #f (member* 'chips '())) (member* 'chips '((chips ((with) fish) (chips)))))
(or (member* 'chips '()) (member* 'chips '((chips ((with) fish) (chips)))))
(or #f (member* 'chips '((chips ((with) fish) (chips)))))
(member* 'chips '((chips ((with) fish) (chips))))
(or (member* 'chips '(chips ((with) fish) (chips))) (member* 'chips '()))
(or (or (eq? 'chips 'chips) (member* 'chips '(((with) fish) (chips)))) (member* 'chips '()))
(or (or #t (member* 'chips '(((with) fish) (chips)))) (member* 'chips '()))
(or #t (member* 'chips '()))
#t

次はちょっと変わった再帰
木のもっとも左にあるアトムを見つけます
cdr側は気にしないのでcar側だけを再帰していて*関数ではありません

(define leftmost
  (lambda (l)
    (cond ((atom? (car l)) (car l))
          (else (leftmost (car l))))))

ふたつのリストが等しいかどうかを判定するeqlist?を作ります
まずは真正直に考えます

eqlist?は、その引数についていくつ質問をしますか。
9つです。

なぜかというと、

各引数は次のいずれかです。
- 空リスト
- アトムがリストにconsされたもの
- リストが別のリストにconsされたもの

なので引数ひとつにつき３通りの質問、質問がふたつで３×３＝９通りとなるわけです
こうです

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

９個の質問を並べるより、３個の質問を入れ子にしたほうがわかりやすそうですが
どうなんでしょうね
同じ式を何度も評価しなくなるし
こんな感じで

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

その後、質問を5つに整理しています
この流れだと、9個の質問を並べた形のほうがいいということなのかもしれません

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

my-eqlist?も整理してみました
あんまりキレイな並びじゃないですね

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

数を0からadd1で作ったり、リストを()からconsで作ったりするように
論理値は#fからorで(または#tからandで)作ると言えそうです
戒律に含まれていないのは利用頻度が低いから？

eqlist?を使うと、ふたつのS式が等しいかどうかを判定するequal?が簡単に書けます
equal?は再定義できないよとエラーになるので名前は変更しました
本ではいったん4つの質問バージョンを書いてから簡単にしていますが省略
なお本では4つの質問をするのがeqlist?と書いてありますがここはequal?の間違い

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

そしてなんと、equal?を使うとeqlist?が簡単に書けてしまうのです
それぞれの関数は小さくて元のeqlist?よりもわかりやすいし
元のeqlist?でも5つの質問をしていたのに、ls-equal?と新しいeqlist?を合わせても
質問が6つしかありません
話がうますぎる気がしますがなにかだまされてないでしょうか

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

疑っているわけではないですが試しておきます
andの評価順は行数の節約のため無視しました

(equal? '((a) b) '((a) b))
(eqlist? '((a) b) '((a) b))
(and (equal? '(a) '(a)) (eqlist? '(b) '(b)))
(and (eqlist? '(a) '(a)) (eqlist? '(b) '(b)))
(and (and (equal? 'a 'a) (eqlist? '() '())) (and (equal? 'b 'b) (eqlist? '() '())))
(and (and (eqan? 'a 'a) (eqlist? '() '())) (and (equan? 'b 'b) (eqlist? '() '())))
(and (and #t #t) (and #t #t))
(and #t #t)
#t

大丈夫そうですね
equal?`には*はついていませんがS式つまりアトムまたは木を扱うようになって
*+くらいはあるというのにキレイなものです
S式を再帰するときはふたつの関数で相互に再帰するというパターンが使えるかも
しれませんので覚えておきます

S式の再帰までやって、再帰だけにしぼった話はここまでとなります
ここまでの話を受けてか、それとも特に関係ないのか、次の戒律が登場

第6の戒律
関数が正しいときのみ簡単化せよ。

当たり前すぎるような気もしてちょっとピンときません
この本はデータ構造を反映したcondにこだわっているので、無駄にcondが含まれていることが多いです
まずは戒律に従って作ってから直せってことでしょう

おなじみremberの改造版が例として取り上げられています
今度はアトムでなく、任意のS式を見つけて削除するもの
ただし、木を深くたどるようなことはせず、トップレベルの要素のみ調べます

第1弾は以下
対象となるリストがラットとは限らないので、木と同じ質問をしています
carで再帰しないのが*関数と違うところ

(define rember
  (lambda (s l)
    (cond ((null? l) (quote ()))
          ((atom? (car l))
           (cond ((ls-equal? (car l) s) (cdr l))
                 (else (cons (car l) (rember s (cdr l))))))
          (else
           (cond ((ls-equal? (car l) s) (cdr l))
                 (else (cons (car l) (rember s (cdr l)))))))))

って最初はこう書かなきゃダメっすか先生

(car l)がアトムでもリストでも同じ処理をしているので二つの節をひとつにまとめることができます

(define rember
  (lambda (s l)
    (cond ((null? l) (quote ()))
          (else
           (cond ((ls-equal? (car l) s) (cdr l))
                 (else (cons (car l) (rember s (cdr l)))))))))

(else (condは取り除くことができますので

(define rember
  (lambda (s l)
    (cond ((null? l) (quote ()))
          ((ls-equal? (car l) s) (cdr l))
          (else (cons (car l) (rember s (cdr l)))))))

となります
まあそうですね、という感じ

このレベルが「簡単化」だとすると
eqlist?をequal?とeqlist?に分けたのは「簡単化」した例ではないのかな
どういう話のつながりだろう

関数が正しく、うまく設計されていれば、簡単に考えることができます。
そして簡単に考えることができれば、今度は間違えにくくなります。

シンプルなのがいいのは間違いないです

eq?と=を使った関数を、eq?と=を関数equal?で置き換えることで一般化できますか？

基本的には大丈夫ってことはわかるんですがなぜここでこれを聞くんでしょうね？
eqan?でも同じことを聞いてましたが
これを聞くことで読者に何を考えさせようとしているんでしょうか