kb84tkhrのブログ

何を書こうか考え中です

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*で本当にもとのリストの構造が反映されたリストが
できあがるのかというのも不安

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

第2の戒律(リストを作るには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に分割していくところを絵にしてみよう
プログラムの動きを追うときは見やすいはず

f:id:kb84tkhr:20160313221403j:plain

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

f:id:kb84tkhr:20160313221414j:plain

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

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

f:id:kb84tkhr:20160313221433j:plain

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

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

(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は常に別のリストになる。

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

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

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

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