Scheme手習い 第８章 究極のlambda（その２）
ここからは継続の話が出てきます。
ノート：
multirember&co
なかなかパッと見では挙動がイメージしにくい。再帰関数だが全体の構造としては
普通の再帰関数では基底部に辿り着くと後は関数値として逆向きに戻りながら計算をしたりリストを生成したりする、ここでは
- 基底部に辿り着くまで新しい関数を作りながら再帰適用して行き
- 基底部に辿り着くと、再帰の前の段で作られた関数を順番に適用し続け
- 最後に最初にmultirember&coに渡された関数を適用し、その関数値が全体の関数値となる
と言う構造になる。
で、再帰しながら作る関数が何をしているかと言うと
- (car lat)がaと等しい場合は、渡された第１引数newlatと、(car lat)と第２引数seenを繋いだリストを前段から渡されたcolを適用する。
- (car lat)がaと等しくない場合は、(car lat)と第１引数newlatを繋ぎ、第２引数seenをそのままに前段から渡されたcolを適用する。
と言う事は、latの要素でaと等しくない物はnewlatに蓄積し、つまりnewlat側はlatからa以外の要素がコピーされ、aと等しい物はseenに蓄積する事となる。
Schemeにおける多値はR5RSで導入されたとの事なので、従来のSchemeでは「aを除いたリスト」と「含まれていたaのリスト」の両方を返す関数を定義する場合、関数値として返す事は出来ず、これら二つの値を引数としてコールバック関数を呼んで貰う形が必要。
ここでのコールバックはイベントを待つ様な類いではないので、関数値が返って来た後の続きの処理であると理解出来る。
a-friendは第２引数が空であると言う述語関数。multirember&coの挙動と合わせて考えると、seenが空、つまりlatの中にaが無かったら#t、latがaを含んでいたら#fとなる。
最初の例は後回しにされているので２番目の例から見て行く。２番目の例はlatが空リストなので、直ぐにcolが適用される。colはa-friendなので第２引数が空リストの場合は#tとなる。
３番目の例は以下の様な引数でそれぞれの関数が適用される。表の左半分は上から下へ順に適用され、一番下で右側半分に移り、次に右半分を上へと適用する。最終的な関数値はこれらの全ての適用を逆向きに戻る事となる。
| 適用順序 | 関数 | 引数a | 引数lat | 継続関数col | 引数newlat | 引数seen | 適用順序 |
|---|---|---|---|---|---|---|---|
| 1 | multirember&co | tuna | (tuna) | a-friend | () | (tuna) | 4 |
| (car lat)はtunaでaと等しい。 | ①(col newlat (cons (car lat) seen)) | seenに足す | 3 | ||||
| 2 | multirember&co | tuna | () | ① | () | () | |
| latは空なのでcolを適用する。 | |||||||
本では①の関数をnew-friendとして定義している。
次の例。
| 適用順序 | 関数 | 引数a | 引数lat | 継続関数col | 引数newlat | 引数seen | 適用順序 |
|---|---|---|---|---|---|---|---|
| 1 | multirember&co | tuna | (and tuna) | a-friend | (and) | (tuna) | 6 |
| (car lat)はtunaでaと等しくない。 | ①(col (cons (car lat) newlat) seen) | newlatに足す | 5 | ||||
| 2 | multirember&co | tuna | (tuna) | ① | () | (tuna) | |
| (car lat)はtunaでaと等しい。 | ②(col newlat (cons (car lat) seen)) | seenに足す | 4 | ||||
| 3 | multirember&co | tuna | () | ② | () | () | |
| latは空なのでcolを適用する。 | |||||||
本ではここでの①の関数をlatest-friendとして定義している。
最初の例を追う。
| 適用順序 | 関数 | 引数a | 引数lat | 継続関数col | 引数newlat | 引数seen | 適用順序 |
|---|---|---|---|---|---|---|---|
| 1 | multirember&co | tuna | (strawberries tuna and swordfish) | a-friend | (strawberries and swordfish) | (tuna) | 10 |
| (car lat)はtunaでaと等しくない。 | ①(col (cons (car lat) newlat) seen) | newlatに足す | 9 | ||||
| 2 | multirember&co | tuna | (tuna and swordfish) | ① | (and swordfish) | (tuna) | |
| (car lat)はtunaでaと等しい。 | ②(col newlat (cons (car lat) seen)) | seenに足す | 8 | ||||
| 3 | multirember&co | tuna | (and swordfish) | ② | (and swordfish) | () | |
| (car lat)はtunaでaと等しくない。 | ③(col (cons (car lat) newlat) seen) | newlatに足す | 7 | ||||
| 4 | multirember&co | tuna | (swordfish) | ③ | (swordfish) | () | |
| (car lat)はtunaでaと等しくない。 | ④(col (cons (car lat) newlat) seen) | newlatに足す | 6 | ||||
| 5 | multirember&co | tuna | () | ④ | () | () | |
| latは空なのでcolを適用する。 | |||||||
実際に評価してみる。
> (let ((a 'tuna) (lat '()) (col a-friend)) (multirember&co a lat col)) #t > (let ((a 'tuna) (lat '(tuna)) (col a-friend)) (multirember&co a lat col)) #f > (let ((a 'tuna) (lat '(and tuna)) (col a-friend)) (multirember&co a lat col)) #f > (let ((a 'tuna) (lat '(strawberries tuna and swordfish)) (col a-friend)) (multirember&co a lat col)) #f >
multirember&coは「latからaを取り除いたリストと取り除いたaのリストを引数にcolを適用する関数」と言える。
colとしてa-friendを用いると、aのリストが空、即ち「aが見つからない」と言う命題になる。
last-friendはaを除いたリストの長さを意味する。
a、latは同じなので、a-friendの代わりにlast-friendが適用され、(last-friend '(strawberries and swordfish) '(tuna))の結果として3が得られる。colで単に第１引数そのものと定義すれば、multiremberと全く同じ。
> (let ((a 'tuna) (lat '(strawberries tuna and swordfish)) (col last-friend)) (multirember&co a lat col)) 3 > (define first (lambda (x y) x)) > (let ((a 'tuna) (lat '(strawberries tuna and swordfish)) (col first)) (multirember&co a lat col)) (strawberries and swordfish) >
第10の戒律
同時に２つ以上の値を集める際には関数を作るべし。
多値が使える現在では当てはまらない戒律かも。
multiinsertLR&co
oldLとoldRは異なる事が前提なのでoldLと一致したらoldRとの比較は行わない。逆も同様。
multirember&coと同様、multiinertLRは関数の適用が巻き戻る時に新しいlatが出来るが、継続を使う時には基底部に達してから今度はcolを連鎖的に呼び出す事で新しいlatを作り、その他の仕事もする。
multiinsertLR&coは「新しく作ったlat、左に挿入した回数、右に挿入した回数を引数にcolを適用する」と言う事なので、各条件式で作るlamdaはこの形式になり、その関数はまたcolを同じ形式で適用する。つまり
- latが空であれば、空、０回、０回としてcolを適用する
- latの先頭がoldLと等しければ、new＋latの先頭+newlatと連結、L+1、Rにcolを適用する
- latの先頭がoldRと等しければ、latの先頭+new+newlatと連結、L、R+1にcolを適用する
- latの先頭がどちらとも等しくなければ、latの先頭とnewlatを連結、L、Rにcolを適用する
となる。
なぜcolの第２と第３の引数は単にLとRなのですか。
…(cdr lat)とすべてのlatに対してLとRは正しい結果となります。
ひとつ前の問答で出て来る収集子の内容を指している。後半の文章は意味が分からない。この時点でのlatに対するmultiinsertLR&Coの答えとしてのLとRと言う意味では加算しないままで正しい。『(cdr lat)と全てのlat』の部分は分からない。
テストの為にcolにnewlat、l、rを返すだけの関数を渡して評価してみる。
> (let ((new 'salty) (oldL 'fish) (oldR 'chips) (lad '(chips and fish or fish and chips))) (multiinsertLR&co new oldL oldR lad (lambda (newlat l r) newlat))) (chips salty and salty fish or salty fish and chips salty) > (let ((new 'salty) (oldL 'fish) (oldR 'chips) (lad '(chips and fish or fish and chips))) (multiinsertLR&co new oldL oldR lad (lambda (newlat l r) l))) 2 > (let ((new 'salty) (oldL 'fish) (oldR 'chips) (lad '(chips and fish or fish and chips))) (multiinsertLR&co new oldL oldR lad (lambda (newlat l r) r))) 2 >
evens-only*&co
*が付くのは木構造を扱う関数。
even?は組み込みの述語として定義されているので、それをそのまま使う。
evens-only*は適用した木に対し偶数の要素のみを抜き出した木を意味する。その木は
- lが空であれば空リスト
- lの先頭がアトムの時
- lの先頭が偶数であれば、それとlの残りから偶数要素のみを抜き出した木を連結した木
- lの先頭が奇数であれば、lの残りから偶数要素のみを抜き出した木
- lの先頭がリストの時、lの先頭から偶数要素のみを抜き出した木とlの残りから偶数要素のみを抜き出した木を結合した木
となる。
> (let ((l '((9 1 2 8) 3 10 ((9 9) 7 6) 2))) (evens-only* l)) ((2 8) 10 (() 6) 2) >
継続関数は偶数だけになった木、全ての偶数の積、奇数の和を渡されるとの事。
まず基底部としては空リストと単位積として１、単位和として０にcolを適用する。ただし積の方はlに少なくとも一つは偶数が入っている事が前提で、lに偶数が含まれない場合を考慮するのであればその積は別途定義する必要がある。
次にlの先頭がアトムの場合。evens-only*では再帰適用した結果をconsしている部分をevens-only*&coの呼び出しにし、引数は(cdr lat)と新規定義の関数。その引数はnewl、p、s。consの部分を最初の引数に、偶数の場合はpに掛けて、奇数の場合はsに足してcolを適用する定義とする。元々evens-only*の結果の部分はnewlとして渡される事になる。
最後にlの先頭がリストの場合だが、この場合は厄介。まず全体として(car l)に対してevens-only*&coを適用するが、(cdr l)に対しても同様にevens-only*&coを適用し、結果を統合すると言う二段構造が必要になる。まず(car l)にevens-only*&coの適用が終わったときに呼ばれる収集子に(car l)側の結果が渡って来る。その収集子の中で今度は(cdr l)に対してもevens-only*&coを適用する。そこで渡す二つ目の収集子で(car l)に対する結果と(cdr l)に対する結果を統合する。二つの収集子は入れ子になっているので二つ目の収集子は(car l)に対する結果と(cdr l)に対する結果の両方にアクセス出来る。ここでは(car l)側の結果に対してaのprefixを付けてal、ap、asとし、(cdr l)側の結果にはdをprefixとしてdl、dp、dsとしている。
> (define the-last-friend (lambda (newl product sum) (cons sum (cons product newl)))) > (let ((l '((9 1 2 8) 3 10 ((9 9) 7 6) 2))) (evens-only*&co l the-last-friend)) (38 1920 (2 8) 10 (() 6) 2) >
lから奇数を除くと((2 8) 10 (() 6) 2)。積は1920。
奇数は9、1、3、9、9、7なので合計は38。本の28は誤記。
