Scheme修行 第11章 おかえりなさい、ようこそショーへ

随分間があいてしまいましたが『Scheme手習い』に引き続き『Scheme修行』を勉強します。続きなだけに章番号まで続きになんですね。

これまでリストに関数を再帰的に適用する場合に空リストから積み上げて結論を得ていました。リストでは右側から考えていた事になります。関数を再帰呼び出しすると考える場合には呼び出しの戻り道で結果を作って行きました。

ここでは結論はリストを右側から考える事で積み上げるとしても、リストの左側に由来する情報が必要なケースを勉強します。

最初の対話をみるとやはり右が生徒の様な気がして来てしまいますが、やっぱり生徒と言う訳ではなさそうです。

ノート：

member?

述語member?の定義をおさらい。言葉にすると：

1. latが空であれば（メンバーである筈は無いので）偽
2. latの先頭がaと等しければ真
3. それ以外の場合はlatの残りの要素にaが含まれているかに依存する

例を実際に評価してみる。

> (member? 'sardines '(Italian sardines spaghetty parsley))
#t
> 

第１歩として固定の値と各要素を操作する例としてmember?が引き合いに出された。

two-in-a-row?

latの次の要素がもしあるなら、それがこの要素と同じかどうかを判定しなければなりません。

ここの「この要素」とはlatの先頭要素であり、次の要素とは２番目の要素を指す。でもis-fisrt?は違う。latの先頭の要素が与えられた引数と同じかを判定している。なので、(car lat)と(cdr lat)にis-firstを適用して始めて最初の判定が出来る事になる。
is-first?を言葉にすると：

1. latが空であれば偽
2. latの先頭要素がaと等しければ真

明示的に２番目の要素を取り出すのに(car (cdr lat))と書く事を避けて補助関数を持ち出している様な印象。
two-in-a-row?（最初の版）を言葉にすると：

1. latが空であれば偽
2. latの第１要素が第２要素と同じであれば真
3. それ以外は第２要素以降のlatに連続要素があるかに依存する

この定義でも問題点は、(cdr lat)が空になった場合にis-firstでも判定して戻ったtwo-in-a-row?で再帰してまた判定するので重複する点にある。(cdr lat)が空の場合は再帰しない様にするためにはis-firstから再帰する、即ち相互再帰にすると言う事らしい。

two-in-a-row?はis-first-b?を適用するだけ。is-first-b?は(car lat)とaが等しくない場合にtwo-in-a-row?を適用する。（-bが何を意味するのか不明）これでtwo-in-a-row?は単にリスト上の比較する位置を進めるだけの役割となる。

次に相互再帰はやめて、最初のtwo-in-a-row?とは扱うリストを一つずらして、最初から取り出した先頭要素と残りのリストの二つを引数として再帰する関数two-in-a-row-b?として再定義する。再帰の際にlatが段々短くなるが、同時に比較対象も次々と変わる。

two-in-a-row?はtwo-in-a-row-b?を呼び出す準備だけをして、実際の仕事はtwo-in-a-row-b?で行う形になった。
実際に評価してみる：

> (let ((lat '(Italian sardines spaghetti parsley)))
    (two-in-a-row? lat))
#f
> (let ((lat '(Italian sardines sardines spaghetti parsley)))
    (two-in-a-row? lat))
#t
> (let ((lat '(Italian sardines more sardines spaghetti)))
    (two-in-a-row? lat))
#f
> (let ((lat '(b d e i i a g)))
    (two-in-a-row? lat))
#t
> 

ここでは比較の対象が再帰の度に変化する関数を習った。

sum-of-prefixes

数字を扱い加算を用いるが同じ構造。
評価してみる。

> (sum-of-prefixes '(1 1 1))
(1 2 3)
> (sum-of-prefixes '(2 1 9 17 0))
(2 3 12 29 29)
> (sum-of-prefixes '(1 1 1 1 1))
(1 2 3 4 5)
> 

第11の戒律

ある関数が、その関数に対する他の引数がいかなるものか知る必要がるときは、付加的な引数を用いるべし。

何となく分かるようで正確には今ひとつ意味が分からない。Google Booksにある原著のプレビューを見ても『Use additional arguments when a function needs to know what other arguments to the function have been like so far.』とあり、ほぼそのままの訳。ただし「have been 〜 so far」の部分は日本語訳には現れていない模様。なので『いかなるものか』の部分は「再帰によってそれまで走査して来た結果」と捉える事にする。two-in-a-rowの場合は最後の要素、sum-of-prefixesの場合にはそれまでの合計。

scramble

関数scrambleの説明がなかなか難しいが、その先も読んでよくよく解釈すると：

1. scrambleはリストを返す関数
2. リストの各要素の値は、その要素の値をnとした時、元のリスト上でその要素から(n-1)左へ遡った要素の値である

となる。なので

• 元のリストのn番目の要素の値はnより大きくはならない→『どの数も自分の位置を示す番号より大きくない』
• 各要素に対して一つずつ値を決める→『同じ長さのタップを返します。』

と言う記述になる。意味が分かってみれば確かにそう書いてはあるがなかなか直ぐに理解できない。
例で示すと：

• ある要素の値が１であれば、自分自身。即ち１
• ある要素の値が２であれば、一つ前の要素の値
• ある要素の値が３であれば、二つ前の要素の値

と言った具合。
各要素に対して再帰的に処理して行くとして、その処理にはその要素よりも左側のリストが必要。ある要素よりも左側のリストを作ったとして、再帰で処理する要素を進めた時にこのリストの末尾に新規の要素を足す必要がある。これは単純にconsでは出来ない。また、そのリストの末尾からn-1番目の値を取り出す必要があるが既出のpickを使う事を考えると、この「左側のリスト」は前後が逆になったリストであると都合が良い。*1

scramble-bは二つの引数を取る。これから処理するタップ（右タップとする）、及び元のタップのそれよりも左側を左右逆にしたタップ（逆左タップとする）。

1. 右タップが空であれば空リスト
2. そうでなければ、
   1. 右タップの先頭要素の数をnとした時に、右タップの先頭要素と逆左タップを繋いだタップのn番目の要素
   2. 右タップの残りの要素、右タップの先頭要素に逆左タップを繋いだタップにscramble-bを適用した結果
   3. 上記の二つを繋いだリスト

実際に評価してみる：

> (let ((tup '(1 1 1 3 4 2 1 1 9 2)))
    (scramble tup))
(1 1 1 1 1 4 1 1 1 9)
> (let ((tup '(1 2 3 4 5 6 7 8 9)))
    (scramble tup))
(1 1 1 1 1 1 1 1 1)
> (let ((tup '(1 2 3 1 2 3 4 1 8 2 10)))
    (scramble tup))
(1 1 1 1 1 1 1 1 2 8 2)
> 

scramble-bを呼び出す時に逆左タップに右タップの先頭要素を足してしまった方が(car tup)を２回適用する手間は省ける筈だが。

*1:勿論元のリストを常に持っていて、今何番目の要素を取り扱っているのか、も再帰の際に渡す事でscrambleを実装する事も可能な筈。