Scheme手習い(12) 継続

 第8章「究極のlambda」の続きの続き

Scheme手習いもそろそろ終盤
継続ってやつが出てきます
中ボスクラス

Schemeはもともと継続を扱う機能を持っているんですが
ここではlambdaを使って継続を手作りします
たぶん原理的には同じもの

では、これはどうでしょう。

(define multirember&co
  (lambda (a lat col)
    (cond ((null? lat) (col (quote ()) (quote ())))
          ((eq? (car lat) a)
           (multirember&co a (cdr lat)
             (lambda (newlat seen) (col newlat (cons (car lat) seen)))))
          (else
            (multirember&co a (cdr lat)
              (lambda (newlat seen) (col (cons (car lat) newlat) seen)))))))

わかりません！

本でも一歩ずつ進めていますが慣れたやりかたで確かめていきます
colには次の関数を入れます

(define a-friend (lambda (x y) (null? y)))

そもそもこの関数が何かって話もありますが細かいことは忘れて進みます
一番簡単なやつから

  (multirember&co 'tuna '() a-friend)
= (a-friend '() '())
= (null? '())
= #t

a-friendというのは最後に呼ばれる関数のようです
たぶんa-friendがやってることには大した意味はなくてただ呼ばれるだけのもの

次は(tuna)を与えます
eq?が成り立ちますね

  (multirember&co 'tuna '(tuna) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (a-friend newlat (cons 'tuna seen))))
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen))) '() '())
= (a-friend '() (cons 'tuna '()))
= (a-friend '() '(tuna))
= (null? '(tuna))
= #f

seenにtunaがconsされました

lambdaの中の引数はさっさと置き換えたけど大丈夫だったかな
最後まで値に置き換えないのが正しいのかもしれない
そうするとこう

  (multirember&co 'tuna '(tuna) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (col newlat (cons (car lat) seen))))
    ;ここでcolはa-friend、latは(tuna)
= ((lambda (newlat seen) (col newlat (cons (car lat) seen))) '() '())
    ;ここでcolはa-friend、latは(tuna)
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen))) '() '())
    ;ここで初めてcolやlatを値に置き換える？
= (a-friend '() (cons 'tuna '()))
= (a-friend '() '(tuna))
= (null? '(tuna))
= #f

式の上に現れない情報があってちょっと書きにくいです
結果は同じでした
すぐ置き換えちゃうことにします

次はeq?が成り立たない引数で

  (multirember&co 'tuna '(and) a-friend)
= (multirember&co 'tuna '()
    (lambda (newlat seen) (a-friend (cons 'and newlat) seen)))
= ((lambda (newlat seen) (a-friend (cons 'and newlat) seen)) '() '())
= (a-friend (cons 'and '()) '())
= (a-friend '(and) '())
= (null? '())
= #t

今度はnewlatにandがconsされました
パターンが見えてきました

普通っぽい引数で

  (multirember&co 'tuna '(tuna and swordfish) a-friend)
= (multirember&co 'tuna '(and swordfish)
    (lambda (newlat seen) (a-friend newlat (cons 'tuna seen))))
= (multirember&co 'tuna '(swordfish)
    (lambda (newlat seen)
      ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
       (cons 'and newlat) seen)))
= (multirember&co 'tuna '()
    (lambda (newlat seen)
      ((lambda (newlat seen)
         ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
          (cons 'and newlat) seen))
       (cons 'swordfish newlat) seen)))
= ((lambda (newlat seen)
     ((lambda (newlat seen)
        ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
         (cons 'and newlat) seen))
      (cons 'swordfish newlat) seen))
   '() '())
= ((lambda (newlat seen)
     ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
      (cons 'and newlat) seen))
   '(swordfish) '())
= ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
   '(and swordfish) '())
= (a-friend '(and swordfish) '(tuna))
= #f

colは最終的に、()にswordfishをくっつけて、andをくっつけて
それとは別に()にtunaをくっつけてからa-friendを呼ぶ関数になりました
リストの後ろのほうからくっつけていくことになるので少しイメージしにくいですが
consを使うとリストの先頭に要素をくっつけていくため
つじつまが合って元の順番を崩さずに要素が取り出せています

colが膨れ上がって見づらくなったので、変数っぽいもので置き換えてみます

  (multirember&co 'tuna '(tuna and swordfish) a-friend)
;ここでcol1 = a-friendとする
= (multirember&co 'tuna '(and swordfish)
                  (lambda (newlat seen) (col1 newlat (cons 'tuna seen))))
;ここでcol2 = (lambda (newlat seen) (col1 newlat (cons 'tuna seen)))とする
= (multirember&co 'tuna '(swordfish)
                  (lambda (newlat seen) (col2 (cons 'and newlat) seen)))
;ここでcol3 = (lambda (newlat seen) (col2 (cons 'and newlat) seen))とする
= (multirember&co 'tuna '()
                  (lambda (newlat seen) (col3 (cons 'swordfish newlat) seen)))
;ここでcol4 = (lambda (newlat seen) (col3 (cons 'swordfish newlat) seen))とする
= (col4 '() '())
= ((lambda (newlat seen) (col3 (cons 'swordfish newlat) seen)) '() '())
= (col3 '(swordfish) '())
= ((lambda (newlat seen) (col2 (cons 'and newlat) seen)) '(swordfish) '())
= (col2 '(and swordfish) '())
= ((lambda (newlat seen) (col1 newlat (cons 'tuna seen))) '(and swordfish) '())
= (col1 '(and swordfish) '(tuna))
= (a-friend '(and swordfish) '(tuna))
= #f

すごくわかりやすくなったのかというとそうでもない気もします
まあ練習練習

(lambda (newlat seen) (col newlat (cons (car lat) seen)))といった関数は
その場では実質的な処理は行ってなくて
あとでこんな風に引数をいじって最後にa-friendを呼び出してね、と言ってるんですね

(multirember&co a lat col)

というのは

• latから、newlatにa以外の要素を、seenにaを集めてcolを適用しろ

という関数です
multirember&coは上の処理を少しだけ簡単にして、multirember&coを呼び出します

(multirember&co a (cdr lat)
  (lambda (newlat seen) (col (cons (car lat) newlat) seen)))

こういう風に理解しました

multirember&coさんはある日、上司から仕事を頼まれました
ひとりでやるのは大変なので、自分そっくりの能力を持つ下請けさんと仕事の相談をします

• あのさあ、上からこんな問題解けって言われたんだよ

latからaを取り除けと言われました

• ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？

(cdr lat)についてだけ解けばいいようにして、下請けさんに仕事を依頼します

• でさあ、答えが出たらオレの分の実作業もやっといてよ

(cons (car lat) newlat)もやっといてねと下請けさんにお願いします

• あとさあ、答えが出たらコレしとけって言われてんだよね
• これもやっといてくんね？

上司に頼まれたcolも下請けさんにやらせようとします
下請けさんも自分でやるのは大変なのでやはり下請けさんとそっくりの能力を持つ
部下と仕事の相談をします

• あのさあ、上からこんな問題解けって言われたんだよ
• ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？
• でさあ、答えが出たらオレの分の実作業もやっといてよ
• あとさあ、答えが出たらコレしとけって言われてんだよね
• これもやっといてくんね？

上司さんがオレさんに頼んだ分とオレさんが下請けさんに頼んだ分までやるように
お願いされてしまいました
下請けさんの部下は困ってしまって二次請けさんの（以下同文）

n次受けさんは

• ()からaを取り除く？ああそれくらい簡単だよ

それはいいんですが

• え、実作業全部オレがやるの？

そうですあなたがやるんです
こういう仕事ね

((lambda (newlat seen)
   ((lambda (newlat seen)
      ((lambda (newlat seen) (a-friend newlat (cons 'tuna seen)))
       (cons 'and newlat) seen))
    (cons 'swordfish newlat) seen))
 '() '())

継続で渡すというのはたいへんな多重請負丸投げ構造だったというわけです
丸投げして結果すら見てないという世界
オマエが返してくる値なんかいらないよと
その代わり値が求まったらその値についてこうしとけと

という理解

ついでに普通の再帰だとどういう理解になるか

(define multirember
  (lambda (a lat)
    (cond ((null? lat) (quote ()))
          ((eq? (car lat) a) (multirember a (cdr lat)))
          (else (cons (car lat) (multirember a (cdr lat)))))))

multiremberさんはある日、上司から仕事を頼まれました
ひとりでやるのは大変なので、自分そっくりの能力を持つ下請けさんと仕事の相談をします

• あのさあ、上からこんな問題解けって言われたんだよ

latからaを取り除けと言われました

• ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？

(cdr lat)についてだけ解けばいいようにして、下請けさんに仕事を依頼します

• 答えが出たら教えてねあとはやっとくから

ここが違います

下請けさんは(cdr lat)からaを取り除くことだけ考えます
とはいえ下請けさんも自分で全部やるのは大変なので部下と仕事の相談をします

• あのさあ、上からこんな問題解けって言われたんだよ
• ちょっとだけ問題を簡単にしとくから、その簡単になった問題解いてくんね？
• 答えが出たら教えてねあとはやっとくから

下請けさんの部下は(cdr (cdr lat))についてだけ解けばいいんですが
でもやっぱり二次請けさんの（以下同文）

n次受けさんは

• ()からaを取り除く？ ()でしょ はいどうぞ

あとはそれぞれが自分の分担に応じてリストにアトムをくっつけたりくっつけなかったりしながら
答えを作って上司さんに答えを返します
健全な社会です

さて話を戻して

colが何を表すか知っていますか。
colは「collector(収集子)」の短縮形です。
収集子は「continuation(継続)」と呼ばれることもあります。

自分が呼び出す関数に、「自分の仕事（＝carを適切な引数にconsする仕事）が
終わったらコレやっとけよ」と関数を渡す
この「コレ」が「継続」ということ

最後の戒律

第10の戒律
同時に２つ以上の値を集める際には関数を作るべし。

関数はひとつの値しか返しませんが継続はいくつもの引数を取れますからね
multirember&coなんか少々不自然な例だなーと思ってましたが
（片方のリストにはtunaしか入らないし）
２つ以上の値を集める例を考えるのに苦労したということでしょうか

とはいっても関数だってリストで複数の値を返せるはず
(newlat seen)という形で値を返す関数を考えてみますよ
a-friendの代わりの関数はこうなります
seenを取り出すには(car (cdr ...))を使います

(define another-friend
  (lambda (newlat-seen)
    (null? (car (cdr newlat-seen)))))

いつものパターンにしたがって

(define multirember-list
  (lambda (a lat)
    (cond ((null? lat) (quote (() ())))
          ((eq? (car lat) a) (

えーと？
multirember-listを呼んで
返ってきた(newlat seen)からseenを取り出してtunaをconsして
またnewlatとconsして返したいんですけど
単純に(car (cdr (multirember-list ...)))としてseenを取り出すと
newlatを忘れてしまいます
何かに記憶しておかないと

手持ちの技だとlambdaの引数に入れるくらいしかなさそう

(define multirember-list
  (lambda (a lat)
    (cond ((null? lat) (quote (() ())))
          ((eq? (car lat) a)
           ((lambda (newlat-seen)
              (cons (car newlat-seen)
                    (cons (cons (car lat) (car (cdr newlat-seen))) '())))
            (multirember-list a (cdr lat))))
          (else
           ((lambda (newlat-seen)
              (cons (cons (car lat) (car newlat-seen))
                    (cons (car (cdr newlat-seen)) '())))
            (multirember-list a (cdr lat)))))))

これでいけるかな？

> (multirember-list 'tuna '(tuna and swordfish))
((and swordfish) (tuna))

> (another-friend (multirember-list 'tuna '(tuna and swordfish)))
#f

いけました

継続とくらべてわかりやすいかっていうとまあなんとも言えないですね
いくつか関数を定義してやれば見やすくはなると思いえますが
そこまで苦労して名前をつけるなら関数の引数にしておけば、って話でしょうか？

multiinsertLR&coは引数が増えただけなので割愛

Scheme手習い(11) 抽象化、部分適用

第8章「究極のlambda」の続き
insertRとinsertLを高階関数に書き換えます

(define insertL-f
  (lambda (test?)
    (lambda (new old l)
      (cond ((null? l) (quote ()))
            ((test? (car l) old) (cons new (cons old (cdr l))))
            (else (cons (car l) ((insertL-f test?) new old (cdr l))))))))

(define insertR-f
  (lambda (test?)
    (lambda (new old l)
      (cond ((null? l) (quote ()))
            ((test? (car l) old) (cons old (cons new (cdr l))))
            (else (cons (car l) ((insertR-f test?) new old (cdr l))))))))

そっくりですね
違うのは要素を挿入する部分、つまり(cons new (cons old (cdr l)))と
(cons old (cons new (cdr l)))だけ
ここを引数として取るような関数insert-g を作ります
（比較はeq?だけに戻っています）

(define insert-g
  (lambda (seq)
    (lambda (new old l)
      (cond ((null? l) (quote ()))
            ((eq? (car l) old) (seq new old (cdr l)))
            (else (cons (car l) ((insert-g seq) new old (cdr l))))))))

するとinsertLとinsertRが以下のように書けるようになります

(define seqL
  (lambda (new old l)
    (cons new (cons old l))))
(define insertL (insert-g seqL))

(define seqR
  (lambda (new old l)
    (cons old (cons new l))))
(define insertR (insert-g seqR))

以下は何を言おうとしているのか

これらの2つの定義にどこか普通ではないことがありますか。

いや別に
何かあります？

はい。

あるんですか

以前でしたら

seqがseqLのとき(define insertL (insert-g seq))

で、

seqがseqRのとき(define insertR (insert-g seq))

としていたでしょう。

今までなら

lのcarは何ですか。
ここで lは((a b c) x y z)です。

とか言ってた類のことかな？
これを実際試すときには(car (quote ((a b c) x y z)))としてたけど
今回はquoteしなくていいですね、ってこと？
((a b c) x y z)は評価されちゃうと困るけど
seqLやらseqRは評価してもらわないと逆に困る

しかし、「のとき」は引数として関数を渡すときには不要です。

「のとき」ってなんじゃらほいという疑問は残る
原文でもwhereだから訳が変ってわけでもなさそうだ
しいて言えば「のとき」以下は、くらいかな

seqL、seqRを他で使うことがないなら、わざわざdefineしないで以下のようにlambdaでも書ける
書けるんだけれども本では触れられない なぜだろう

(define insertL (insert-g (lambda (new old l) (cons new (cons old l)))))
(define insertR (insert-g (lambda (new old l) (cons old (cons new l)))))

lambdaもquoteしない
当たり前といえば当たり前だけれども
考え過ぎるとゲシュタルト崩壊みたいな気分になる

では、

次のyyyについてはどう思いますか。

(define yyy
  (lambda (a l)
    ((insert-g seqrem) #f a l)))

(define seqrem
  (lambda (new old l)
  l))

驚きです。これは

よく知っているremberではありませんか！
ちょっと意表をつかれた

newは使われないんだけど何か引数を書かないといけないから#fを渡している

これまでに見たことこそ抽象化の力です。

insertLとinsertRとsubstとremberは実はそっくりさんだった、というお話でした

第９の戒律
新しき関数においては共通のパターンを抽象化すべし。

DRY原則、かな
いよいよ戒律も残すはあとひとつ

次はvalueをネタにして第９の戒律の練習

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (operator aexp) (quote +))
          (o+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote *))
          (o* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote ^))
          (o^ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))))))

+の行と*の行と^の行がそっくりで、+、*、^に応じてo+、o*、o^を使い分けているだけだから
そういう関数を作ってやります

(define atom-to-function
  (lambda (x)
    (cond ((eq? x (quote +)) o+)
          ((eq? x (quote *)) o*)
          (else o^))))

これを使うとvalueはこうなります

(define value
  (lambda (nexp)
    (cond ((atom? nexp) nexp)
          (else ((atom-to-function (operator nexp))
                 (value (1st-sub-exp nexp))
                 (value (2nd-sub-exp nexp)))))))

演算子を増やすときはatom-to-functionだけを変更すればいいし
前置記法に書き換えたい場合はvalueだけを（しかも1箇所だけを）変更すればよくなりました

D・R・Y!
D・R・Y!

multiremberのeq?を引数で指定できるようにしたmultirember-fを作ります

(define multirember-f
  (lambda (test? a lat)
    (cond ((null? lat) (quote ()))
          ((test? (car lat) a)
          (multirember-f test? a (cdr lat)))
          (else
          (cons (car lat) (multirember-f test? a (cdr lat)))))))

> (multirember-f = 2 '(1 2 3 2))
(1 3)

(test? xxx a)という部分をまとめて関数にしてしまえば、test?とaを別にして渡す必要がなくなります

(define multiremberT
  (lambda (test? lat)
    (cond ((null? lat) (quote ()))
          ((test? (car lat))
          (multiremberT test? (cdr lat)))
          (else
          (cons (car lat) (multiremberT test? (cdr lat)))))))

> (multiremberT (lambda (a) (= a 2)) '(1 2 3 2))
(1 3)

関数の部分適用てやつですかね
こっちの書き方のほうが適用範囲が広がりそうです

Scheme手習い(10) 高階関数とカリー化

第8章「究極のlambda」では高階関数を学びます

まずは一番わかりやすい、引数として関数を渡すパターン
いつものremberで、比較のための関数を指定できるようにします

(define rember-f
  (lambda (test? a l)
    (cond ((null? l) (quote ()))
          ((test? (car l) a) (cdr l))
          (else (cons (car l) (rember-f test? a (cdr l)))))))

動かします

> (rember-f = 5 '(6 2 5 3))
(6 2 3)
> (rember-f eq? 'jelly '(jelly beans are good))
(beans are good)
> (rember-f equal? '(pop corn) '(lemonade (pop corn) and (cake)))
(lemonade and (cake))

この本はeq?で数字の比較はできないという姿勢を貫いてます

次は、関数を返すパターン

では、

(lambda (a)
  (lambda (x)
    (eq? x a)))

は何ですか。

ラムダラムダって何

引数としてaを渡されると関数

(lambda (x)
(eq? x a))

を返します。ここでaは渡された引数です。

具体例で考えてみます

(lambda (a)
  (lambda (x)
    (eq? x a)))

に引数1を与える、つまり以下の関数適用は

((lambda (a)
  (lambda (x)
    (eq? x a))) 1)

以下の関数、つまりxと1が等しいかどうかを返す関数を返します

(lambda (x)
  (eq? x 1))

ってことはつまりアレか
ラムダラムダにびっくりせずいつもどおりのやり方でいいんだ

((lambda (a) (lambda (x) (eq? x a))) 1)
(lambda (x) (eq? x 1))

この関数にもうひとつ引数を与えてやれば、その引数が1と等しいかどうかが返されるわけだ

> (((lambda (a)
      (lambda (x)
        (eq? x a))) 1) 1)
#t
> (((lambda (a)
      (lambda (x)
        (eq? x a))) 1) 2)
#f

つまり、1引数の関数を入れ子にして使うことで

> ((lambda (x a)
    (eq? x a)) 1 1)
#t
> ((lambda (x a)
    (eq? x a)) 1 2)
#f

こういう2引数の関数と同じ働きをすることが可能ってわけね

これは「カリー化」(Curry-ing)と呼ばれています。ありがとう、Schönfinkel(1889〜1942)。

Schönfinkelさんとは誰だろう
Wikipediaより

カリー化 - Wikipedia

カリー化 (currying, カリー化された=curried) とは、複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること（あるいはその関数のこと）である。クリストファー・ストレイチーにより論理学者ハスケル・カリーに因んで名付けられたが、実際に考案したのはMoses Schönfinkelとゴットロープ・フレーゲである。

だそうで
知りませんでした

名前をつけてもOK

(define eq?-c
  (lambda (a)
    (lambda (x)
      (eq? x a))))
(define eq?-salad (eq?-c 'salad))

> (eq?-salad 'salad)
#t
> ((eq?-c 'salad) 'salad)
#t

普通のSchemeの本ならここで何かを説明するはずなんだけど内緒だ
気にしなければどうということもない
関数が関数を返し、そのまま関数として使われるあたりとても関数型っぽい

3引数でやったらどうなるかな
理屈は同じはず
練習してみる

(define eq3?
  (lambda (c)
    (lambda (b)
      (lambda (a)
        (and (eq? a b) (eq? b c))))))
(define eq3?-1 (eq3? 1))
(define eq3?-2 (eq3?-1 1))

> (((eq3? 1) 1) 1)
#t
> ((eq3?-1 1) 1)
#t
> (eq3?-2 1)
#t

次はさっき書いたrember-fのカリー化

(define rember-f
  (lambda (test?)
    (lambda (a l)
      (cond ((null? l) (quote ()))
            ((test? (car l) a) (cdr l))
            (else (cons (car l) ((rember-f test?) a (cdr l))))))))

動かす

> ((rember-f =) 5 '(6 2 5 3))
(6 2 3)

こう書き換えたから何がいいの、ってことはこの本は書いてくれないんで
挙げられてる例から読み取っていくしかないんですけど
最初に出てきたrember-fだと上に出てきたような呼び出し方はできなくて

(define rember= (lambda (a l) (rember-f = a l)))

などとして定義してから(rember= 5 '(6 2 5 3))として呼び出してやるしかありません
同じようにdefineしてから使うにしても、カリー化したrember-fであれば

(define rember= (rember-f =))

と書けてずいぶん身軽になった感じがします
これってポイントフリーとかいうやつでしょうか？違うかな

呼び出しは(rember= 5 '(6 2 5 3))でまったく同じ
同じ書き方で呼び出せて同じ値を返すってことは、まったく同じ関数とみなせますね

Scheme手習い(9) 集合と関数

第7章「友達と親類」では集合と関数を題材に取ります
プログラミング的にはあまり新しい話はない気がするので何を書いたらいいものやら
作者の狙いは何
ここまでで覚えた書き方で数学の概念がこんな風に表現できますよ、みたいな感じ？
私はそういう話好きだからいいんですけど

淡々といきます

(define set?
  (lambda (lat)
    (cond ((null? lat) #t)
          ((member? (car lat) (cdr lat)) #f)
          (else (set? (cdr lat))))))

set(集合)とはlatであって要素に重複がないもの、という定義です

latかどうか（要素がアトムかどうか）は数学とは関係ないですけどね
latだけどequal?で判定してるから数だってOKだよ、とも書いてあります
じゃあリストが要素になっても悪くはなそうですが
この本ではそういうことになってるということでまあ

latの要素に重複があったら取り除いてsetにするmakeset

(define makeset
  (lambda (lat)
    (cond ((null? lat) (quote ()))
          ((member? (car lat) (cdr lat)) (makeset (cdr lat)))
          (else (cons (car lat) (makeset (cdr lat)))))))

こんなに短くて驚きましたか。

そうでもないですがmember?が使えなかったらもっと長くなりますね

実行すると少し直感に反する順番の結果になります

> (makeset '(apple peach pear peach plum apple lemon peach))
'(pear plum apple lemon peach)

こちらの定義ならすんなりした結果
でもソース的には上のほうが好きかなあ

(define makeset
  (lambda (lat)
    (cond ((null? lat) (quote ()))
          (else (cons (car lat)
                      (makeset (multirember (car lat) (cdr lat))))))))

> (makeset '(apple peach pear peach plum apple lemon peach))
'(apple peach pear plum lemon)

set1がset2のsubset(部分集合)である、とは

(define subset?
  (lambda (set1 set2)
    (cond ((null? set1) #t)
          (else (and (member? (car set1) set2)
                     (subset? (cdr set1) set2))))))

set1のすべての要素がset2に含まれているということ

このへん、いちいち(else (condと書いてから簡単化してます
まだ千本ノックが続いてるということでしょうか
subset?ではさらにandを使って(else #f)を消す、ということもやってます
元はこれ

(define subset?
  (lambda (set1 set2)
    (cond ((null? set1) #t)
          ((member? (car set1) set2) (subset? (cdr set1) set2))
          (else #f))))

andで書いたほうがいいんでしょうかね
まあ(else #f)っていうのが余分感あるってのは思いますが
気分的なもの以外に差は？

set1とset2が等しい、とはset1がset2のsubsetであり、かつset2がset1のsubsetである、ということ

感覚的には「set1とset2に同じ要素が含まれていること」なんですが
そのままだとプログラムにしにくいですね

数学でもこういう書き方よく出てきます
そう言わないと数学的に言ってもあいまいってことなんでしょうか

(define eqset?
  (lambda (set1 set2)
    (cond (else (and (subset? set1 set2) (subset? set2 set1))))))

(cond (elseはどうしても書かずにいられないんでしょうか
そのわりには戒律にもなってないし
condがない関数なんかインラインに展開すればいいんだよとかそういう話なんでしょうか
求む解説

(define eqset?
  (lambda (set1 set2)
    (and (subset? set1 set2) (subset? set2 set1))))

これね

set1とset2が交わっている(intersect?)とは、set1とset2に共通の要素があるということ
プログラムで書くと、set1の要素のうちどれかがset2の要素であること、ということになります
set2の要素のうちどれかがset1の要素であること、でも同じ

(define intersect?
  (lambda (set1 set2)
    (cond ((null? set1) #f)
          (else (or (member? (car set1) set2)
                    (intersect? (cdr set1) set2))))))

subset?とintersect?を比べてください。

ほほう
andとor、#tと#fが入れ替わってるだけですね
こういう関係はandとorまで持っていったからわかると言えるかもしれません

続いてintersect(積集合)、union(和集合)、xxx(差集合)を定義します

ここまで集合の話
ここからだんだんと関数の話になっていきます
関数と言っても関数型プログラミングというときの関数とも高校で習う数学の関数とも
イメージが異なります
集合を使って関数を定義してやろうという話

ペアは2つのS式だけからなるリスト
ただし

Scheme (あるいはLisp) のペアは関係はありますが別のものです

Schemeのペアというのは(a . b)って表わされるやつですね
(cons 'a 'b)で作るやつ
上で言う「ペア」は(cons 'a (cons 'b '())で作るものです

さらに、ペアの左の要素を取るfirst、右の要素を取るsecond、ペアを作るbuildを定義
まだ(cond (else が出てきます
なにが作者にそこまでさせているのか

relation(関係)とはペアの集合

なんでペアの集合が関係なのか
たとえば1、2、3という数の中で大小の関係を定義するとすれば
((1 2) (1 3) (2 3))という集合を定義して
この集合にfirst = a、second = bとなる要素があるときa < bとする
と決めてやれば大小の関係を定義したことになります

って話

なぜか本にはrel?という関数は出てきません
なぜでしょうか
こんな感じかと思うんですが何か落とし穴があったりするんでしょうか

(define rel?
  (lambda (rel)
    (cond ((null? rel) #t)
          ((not (a-pair? (car rel))) #f)
          ((member? (car rel) (cdr rel)) #f)
          (else (rel? (cdr rel))))))

この本ではnotが定義されてないので若干反則気味
notを使わなくても書けなくはないですがなんとなく
set?を使う手もあるか

notを定義するならこうかな

(define not
  (lambda (x)
    (cond (x #f)
          (else #t))))

これはandやorと違って普通に関数で書いても大丈夫

さていよいよ関数

有限関数とは、ペアのリストであって、各ペアの第1要素はほかのどのペアの第1要素とも
同じでないものと表現できます

数学では無限集合だって自由に考えられるので有限に限ることはないんですが
リストで表現するとどうしても有限集合になってしまいますね
遅延リストだったら無限集合も表現できるかな？
でも所詮は加算無限までだろう
たぶん実用（って実用なのかこの本は）的にはあんまり意味なさそう
リスト内包表記だったら？
それはちょっとここでやろうとしていることと合ってない気がする

あと、流れからすれば「関係であって」とか「ペアの集合であって」だと思いますが、
各ペアの第1要素が一意なので結局同じことですね
関数定義ではrelってことになってます
「各ペアの第1要素はほかのどのペアの第1要素とも同じでないもの」はset?で判定

(define fun?
  (lambda (rel)
    (set? (firsts rel))))

y = f(x)みたいな関数とはイメージが異なりますが
関数をxを与えればyが決まるもの、とシンプルに考えて
第1要素をx、第2要素をyと考えれば確かに関数と言えます
第1要素が同じペアが複数あるとyがひとつに決まらなくなってしまうので困ります

revrel(不勉強にして対応する日本語が思いつきません 逆関係？でいいのかな？)とは
関係に含まれるペアの第1要素と第2要素を入れ替えたもの

(define revrel
  (lambda (rel)
    (cond ((null? rel) (quote ()))
          (else (cons (build (second (car rel)) (first (car rel)))
                      (revrel (cdr rel)))))))

入れ替え部分を抽象化したrevpairを導入
こういうことは日頃からこころがけていきたいものです

(define revpair
  (lambda (pair)
    (build (second pair) (first pair))))

(define revrel
  (lambda (rel)
    (cond ((null? rel) (quote ()))
          (else (cons (revpair (car rel))
                      (revrel (cdr rel)))))))

全単射とは、関数であって値に重複がないもの、という定義

(define fullfun?
  (lambda (fun)
    (set? (seconds fun))))

引数の名前をfunにしただけで定義域は関数であると空気を読まなければいけません

いきなり全単射が出てくるとアレですね

• 全射
  y（さっきそう呼んでたもの）が取りうる値すべてに対し、対応するxがあることです
  ここの定義だとこれは最初から満たされてます
• 単射
  どのyに対しても、対応するxがせいぜい1個しかないということです
  ここの定義で言えばsecondに重複がないことですね

全射と単射を満たすとき全単射と言います

fullfunは素直に考えてfull functionだと思うんですが
それが部分関数(partial function)に対する全関数だとすると話と合わない
どこか理解が間違ってるのかな・・・
（実は全射とか単射がどうもちゃんと覚えられない）

fullfun?の別の名前は何でしょう。

one-to-one? (一対一対応)です。

全単射＝一対一対応です
これはまちがいない
全関数と一対一対応は違うよな・・・

(define one-to-one?
  (lambda (fun)
    (fun? (revrel fun))))

(revrel fun)のことは逆関数と言いますね

オチなし

Scheme手習い (8) 表現と抽象化

基本的な再帰の練習は5章までで終わり
第6章「影法師」からは応用編といった感じ
6章では算術式を題材にして表現と抽象化を学びます

算術式をschemeで取り扱うためにS式で表したものを算術式の表現と呼びます
まずは単純に、n + 3を(n + 3)と表現します
ということは1 + 2 + 3の表現は(1 + 2 + 3)かと思ったらハズレ

ここでは「2つの（数を含む）アトムか算術式を+か*か^で結合したもの」を算術式と呼んでます
算術式の定義に算術式が出てきますので再帰的定義ですね
こういうのが後から出てくるのがこの本の特徴

1 + 2 + 3は算術式1 + 2と算術式3を+で結合したものか、
または算術式1と算術式2 + 3を+で結合したものとみなせるので
その表現は((1 + 2) + 3)か(1 + (2 + 3))のどちらかになります

右から結合とか左から結合とかは決まっていないようなので
元の式がどちらかの意味なのかはわかりませんが
表現になっているものは必ずそれぞれの算術式がカッコで囲まれるためあいまいさはありません

まずは算術式が数からのみなる式かどうかを判別するnumbered?を考えます
この関数の定義域は算術式
この本では定義的に入らない入力についてはたいていなんの考慮もされません
そのことがわかっていないと穴埋めもできなかったりします

(define numbered?
  (lambda (aexp)
    (cond ((atom? aexp) (number? aexp))
          ((eq? (car (cdr aexp)) (quote +))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote *))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote ^))
           (and (numbered? (car aexp)) (numbered? (car (cdr (cdr aexp)))))))))

定義を忠実になぞってる感じですね

演算子のところが'-'だったらどうするの？
aexpに4つめの要素があったら？
そんな入力は存在しないのです

ちゃんとした算術式であることをアテにできるのならもっと短く書けます

(define numbered?
  (lambda (aexp)
    (cond ((atom? aexp) (number? aexp))
          (else (and (numbered? (car aexp))
                     (numbered? (car (cdr (cdr aexp)))))))))

なぜ簡単化ができるのでしょうか。
関数を正しく把握してきたと知っているからです。

そんなもんですかね
ちょっとピンときません

次は算術式の値を求めます
今度の定義域は、numbered?である算術式
構造は（最初の）numbered?とまったく同じ

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (car (cdr aexp)) (quote +))
           (o+ (value (car aexp)) (value (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote *))
           (o* (value (car aexp)) (value (car (cdr (cdr aexp))))))
          ((eq? (car (cdr aexp)) (quote ^))
           (o^ (value (car aexp)) (value (car (cdr (cdr aexp)))))))))

再帰的な構造を再帰で処理しているからとてもシンプルになります

第7の戒律
性質を同じくするすべての構成部分について再帰すべし。
すなわち、
* リストのすべての部分リストについて。
* 算術式のすべての部分式について。

ここで、算術式の表現を変え、Lispのように演算子を先に書く表現にしてみます
(+ 1 (+ 2 3))みたいな感じ
carとcdrの数で調整しても正しく動作するプログラムは書けますが・・・

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (car aexp) (quote +))
          (o+ (value (car (cdr aexp))) (value (car (cdr (cdr aexp))))))
          ((eq? (car aexp) (quote *))
          (o* (value (car (cdr aexp))) (value (car (cdr (cdr aexp))))))
          ((eq? (car aexp) (quote ^))
          (o^ (value (car (cdr aexp))) (value (car (cdr (cdr aexp)))))))))

ここでは第1の部分式、第2の部分式、演算子をあらわす関数を作って抽象化します

(define 1st-sub-exp
  (lambda (aexp) (car (cdr aexp))))

(define 2nd-sub-exp
  (lambda (aexp) (car (cdr (cdr aexp)))))

(define operator
  (lambda (aexp) (car aexp)))

(define value
  (lambda (aexp)
    (cond ((atom? aexp) aexp)
          ((eq? (operator aexp) (quote +))
          (o+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote *))
          (o* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote ^))
          (o^ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))))))

抽象化を行ったことにより、表現が隠蔽されました
補助関数1st-sub-exp、2nd-sub-exp、operatorを書き換えることにより
valueはそのままでも最初の表現を利用することができます
こうするだけ

(define 1st-sub-exp
  (lambda (aexp) (car aexp)))

(define 2nd-sub-exp
  (lambda (aexp) (car (cdr (cdr aexp)))))

(define operator
  (lambda (aexp) (car (cdr aexp))))

第8の戒律
表現から抽象化するに際し、補助関数を使用すべし。

さらに抽象化が進みます
実用性なんて飾りです

前にも表現を見ましたか。
はい。ただそれが表現だとは言いませんでした。

数は表現ですか。
はい。たとえば、4は4という概念を表します。

ほかには何を使うことができるでしょうか。
(() () () ())でも同様に使えます。((((()))))はどうでしょう。あるいは(I V)では。

というわけで、(() () () ())式の表現を使ってzero?、add1、sub1の代わりの関数を書いてみます

(define sero? (lambda (n) (null? n)))
(define edd1 (lambda (n) (cons (quote ()) n)))
(define zub1 (lambda (n) (cdr n)))

これでo+を書くことができます

(define o+
  (lambda (n m)
    (cond ((sero? m) n)
          (else (edd1 (o+ n (zub1 m)))))))

ちゃんと動くかな

> (o+ '(() ()) '(() () ()))
(() () () () ())

ちゃんと動いてますね

o+の定義は変わりましたか。
はいであり、いいえでもあります。変わりましたがほんの僅かです。

変わったのはzero?がsero?になったように、関数の名前だけ
本来なら僅かも変えずにすむはず
定義済みの関数と名前がかぶっては困るので名前が変えてあるだけです
僅かも変えずにすむことを確かめておきましょう

アラビア数字で数を表現した場合に合わせてsero?ほかを書き換えてやります

(define sero? zero?)
(define edd1 (lambda (n) (+ n 1)))
(define zub1 (lambda (n) (- n 1)))

と定義を変更すればさっきのo+には修正を加えずに

> (o+ 2 3)
5

と計算できます

ついでにo*とo^も作ってvalueまで動かしてやろう
0も表現を隠蔽してやりますかね
(() () () ())式表現ではatom?で判定することができないので
代わりにmumber?という関数を作りました

(define zero (quote ()))
(define sero? (lambda (n) (null? n)))
(define edd1 (lambda (n) (cons (quote ()) n)))
(define zub1 (lambda (n) (cdr n)))
(define mumber?
  (lambda (n)
    (cond ((atom? n) #f)
          ((null? n) #t)
          (else (and (null? (car n)) (mumber? (cdr n)))))))

(define one (edd1 zero))
(define o+
  (lambda (n m)
    (cond ((sero? m) n)
          (else (edd1 (o+ n (zub1 m)))))))
(define o*
  (lambda (n m)
    (cond ((sero? m) zero)
          (else (o+ n (o* n (zub1 m)))))))
(define o^
  (lambda (n m)
    (cond ((sero? m) one)
          (else (o* n (o^ n (zub1 m)))))))

(define value
  (lambda (aexp)
    (cond ((mumber? aexp) aexp)
          ((eq? (operator aexp) (quote +))
           (o+ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote *))
           (o* (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp))))
          ((eq? (operator aexp) (quote ^))
           (o^ (value (1st-sub-exp aexp)) (value (2nd-sub-exp aexp)))))))

さてこれでvalueが動くはず

> (value '((((()) + (() ())) ^ (() ())) * (() ())))
(() () () () () () () () () () () () () () () () () ())

よし
これでzero、sero?、edd1、zub1、mumber?の定義を変えてやれば

(define zero 0)
(define sero? zero?)
(define edd1 (lambda (n) (+ n 1)))
(define zub1 (lambda (n) (- n 1)))
(define mumber? number?)

valueはそのままでアラビア数字の表現を使えるはず

> (value '(((1 + 2) ^ 2) * 2))
18

満足満足

今度の新しい数のもとで(1 2 3)はなんと表現しますか。
((()) (() ()) (() () ()))

(lat? l)は何ですか、ここで
lは((()) (() ()) (() () ()))です。
まさに偽です。

数のリストのはずなのに変ですね。
影法師に注意しなければなりません。

影法師ってなんだろうと思いましたが原書ではただのShadowsでした

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?でも同じことを聞いてましたが
これを聞くことで読者に何を考えさせようとしているんでしょうか

Scheme手習い (6) 一般のリストの再帰

第5章「*すごい*星がいっぱいだ」では一般のリストに対する再帰を練習します
ちょっと苦手なんです

一般のリストってなんでしょう？
ラットやタップと異なり、リストの要素にリストを含むようなもののことを言ってます
S式のリストと書いてるところもあります
なんか同語反復っぽい気がしないでもないですがアトムじゃないよってことでしょうか
木と言ってもいいかもしれない いいんだっけか？
まあ長たらしいので以下では木と言うことにします

この本では、木の内部の個々のアトムまで遡って処理する関数には*(スター)をつけてます
今までとは、carをatom?で判定してるところと
consでcarの再帰とcdrの再帰をくっつけてるところが違いますね

(define rember*
  (lambda (a l)
    (cond ((null? l) (quote ()))
          ((atom? (car l))
           (cond ((eq? (car l) a) (rember* a (cdr l)))
                 (else (cons (car l) (rember* a (cdr l))))))
          (else (cons (rember* a (car l))
                      (rember* a (cdr l)))))))

実行の様子
carとcdrのところで桁をそろえてみました
ラットを処理する関数ではcdr方向に再帰するだけでしたが
木ではcar方向にも再帰を行うので、処理全体をイメージしづらくなりました

(rember* 'b '((a b) (b c)))
(cons (rember* 'b '(a b))         (rember* 'b '((b c))))
(cons (cons 'a (rember* 'b '(b))) (cons (rember* 'b '(b c))        (rember* 'b '())))
(cons (cons 'a (rember* 'b '()))  (cons (rember* 'b '(c))          '()))
(cons (cons 'a '())               (cons (cons 'c (rember* 'b '())) '()))
(cons '(a)                        (cons (cons 'c '())              '()))
(cons '(a)                        (cons '(c)                       '()))
(cons '(a)                        '((c)))
'((a) (c))

答えは合ってるんですけれどもどうも処理全体をイメージできません

何箇所も一度に書き直してるのがよくないのかもしれないので一度に1箇所ずつ
consのところはcarを処理してからcdrを処理するように書いてみますか
たぶんインタプリタはそういう順番で処理しているんじゃないかな

(rember* 'b '((a b) (b c)))
(cons (rember* 'b '(a b))         (rember* 'b '((b c))))
(cons (cons 'a (rember* 'b '(b))) (rember* 'b '((b c))))
(cons (cons 'a (rember* 'b '()))  (rember* 'b '((b c))))
(cons (cons 'a '())               (rember* 'b '((b c))))
(cons '(a)                        (rember* 'b '((b c))))
(cons '(a)                        (cons (rember* 'b '(b c))        (rember* 'b '())))
(cons '(a)                        (cons (rember* 'b '(c))          (rember* 'b '())))
(cons '(a)                        (cons (cons 'c (rember* 'b '())) (rember* 'b '())))
(cons '(a)                        (cons (cons 'c '())              (rember* 'b '())))
(cons '(a)                        (cons '(c)                       (rember* 'b '())))
(cons '(a)                        (cons '(c)                       '()))
(cons '(a)                        '((c)))
'((a) (c))

理解度はあんまり変わらなかったよ
練習にはなったかな・・・
ちょっと先に進んでみます

oldと一致するアトムの右側にnewを挿入するinsertR*です
構造はrember*と同じ

(define insertR*
  (lambda (new old l)
    (cond ((null? l) (quote ()))
          ((atom? (car l))
           (cond ((eq? (car l) old)
                  (cons old (cons new (insertR* new old (cdr l)))))
                 (else
                  (cons (car l) (insertR* new old (cdr l))))))
          (else (cons (insertR* new old (car l))
                      (insertR* new old (cdr l)))))))

これも、1行ずつ見ている限り正しいに違いないとは思うんですけど
全体としてちゃんと動くイメージがどうも浮かばないんですよね

千本ノック状態は続いてますから書くことには慣れてくるんですけど
なんかこう、carとcdrが対称なような非対称なような・・・
非対称なんだけれども考えているうちに頭の中では対象なものと考えてしまうような
なんか引っかかりがね

どの*関数も、一般のリスト、つまり次のいずれかの上で動くからです。

• 空リスト
• アトムがリストにconsされたもの
• リストが別のリストにconsされたもの

これですべての場合を尽くしていることもわかるし
それぞれの場合について正しくプログラムされていることもわかるし
carとcdrを取っていけばいつかはアトムか()にたどりつくこともわかる

だから理屈上ちゃんと動くはずなんだけど
関数全体としてどんなリストが与えられてもきちんとすべての要素を回ってくれるね、と
いうところまでイメージが湧かない
rember*やinsertR*で本当にもとのリストの構造が反映されたリストが
できあがるのかというのも不安

プログラム以前に、データ構造がちゃんとイメージできてないのかもしれない
一歩下がって考えなおしてみよう

第２の戒律（リストを作るにはconsを用いるべし）を思い出してconsで書いてみる
((a b) c (d (e f)))というリストならこう

(cons
  (cons 'a (cons 'b '()))
    (cons 'c
      (cons
        (cons 'd
          (cons
            (cons 'e (cons 'f '()))
            '()))
        '())))

あまりわかりやすくなった気がしない

リストをcarとcdrに分解して処理していくんだから
リストをcarとcdrに分割していくところを絵にしてみよう
プログラムの動きを追うときは見やすいはず

途中経過のリストを消すと（絵的に）木っぽくなる
cdr側がちょっとめんどくさい

やっぱりcarとcdrの差がどうも頭にひっかかる
()は正味の情報として無駄とも言えるので詰めて書いちゃえば非対称な感じが消せるかな
消したらわかりやすくなるのかというとそうでもない

Lispでよく出てくる書き方（より矢印が多め）
アトムとリストの区別が明示されて、cdrの先はリストのみということが見やすくなりました
自分で書いてみると意外と最初は書けなくて小さいリストで練習したりしてます
やっぱ苦手
上の図を45度傾けると実は同じ形なんですが

できあがってみるとこれがいちばんわかりやすいかな

何度か図を描いているうちになんとなくはわかってきたので
単純な関数で追いかけてみます

(define copy*
  (lambda (l)
    (cond ((null? l) (quote ()))
          ((atom? (car l)) (cons (car l) (copy* (cdr l))))
          (else (cons (copy* (car l)) (copy* (cdr l)))))))

carをたどったあとcdrをたどり、cdrから戻ったらcons、という風に指でたどっていきます
すべてのアトムを訪れていく様子が実感できます

さっきはわかりづらかったconsによる表現も、copy*が返すリストを作っていく様子だと思えば
元のリストと同じ構造を作っていることを理解する手がかりになります

carとcdrの非対称はアトムはcarにだけ現れてcdrにはリストしか現れないというところですね
考えてみると掟に書いてありました
反芻反芻

Cdrの掟
関数cdrは空でないリストについてのみ定義される。
空でないリストのcdrは常に別のリストになる。

納得したところで第１、第４の戒律の最終版です

第１の戒律（最終版）
アトムのリストlatを再帰せし時は、2つの質問(null? lat)とelseを行うべし。
数nを再帰せしときは、2つの質問、(zero? n)とelseを行うべし。
S式のリストlを再帰せしときは、3つの質問、(null? l)、(atom? (car l))、elseを行うべし。

第４の戒律（最終版）
再帰のときは少なくとも１つの引数を変えるべし。
アトムのリストlatを再帰せしときは、(cdr lat)を用いるべし。
数nを再帰せしときは(sub1 n)を用いるべし。
S式のリストlを再帰せしときは、(null? l)も(atom? (car l))も真でないならば、(car l)と(cdr l)を用いるべし。
必ず最終条件に向かって変化すべし。
変化せし引数は、必ず最終条件でテストすべし。すなわち、
cdrを用いるときは、最後にnull?で、
sub1を用いるときは、最後にzero?でテストすべし。

最終版ということはこれで再帰はパターンを尽くしたってことでしょうか