Scheme手習い 第9章 ……もう一度、もう一度、もう一度、……(その1)
まずは宝探しの様な不思議な再帰関数。
ノート:
looking
lookingの説明は明確には無いが、lookingの挙動を言葉にすると:
- latの1番目の要素から初めて
- その要素が数字であれば、次にその数字番目の要素を見る
- その要素が数字でなければ、aと比較して同じであれば#t、異なれば#f
つまり宝探しの地図の様に最初の要素から開いて、目的地に行き、また地図を開いて、、、最終的に目的の宝に辿り着くか否かと言う述語。#tか#fを返すので述語ではあるが名前に?は付いていない。lookingと言う名前も手続き的で単に宝探しに成功したか失敗したかの結果を返しているだけの様子。
(pick n lat)はlatのn番目の要素。
pickはSchemeのライブラリは存在しないので、以下の定義とする。
(define pick (lambda (n lat) (list-ref lat (sub1 n))))
pickは1始まりなのに対しlist-refは0始まりな所に注意。引数の順番も逆。
まずはpickを実際に評価してみる。
> (pick 1 '(a b c)) a > (pick 2 '(a b c)) b > (pick 3 '(a b c)) c > > (let ((lat '(6 2 4 caviar 5 7 3))) (pick 6 lat)) 7 > (let ((lat '(6 2 4 caviar 5 7 3))) (pick 7 lat)) 3 >
補助関数keep-lookingの定義を言葉にすると:
- 引数sornが数字であれば、latのsorn番目の要素を引数にkeep-lookingを適用した物
- 引数sornが数字でなければ、「aとsornが等しい」と言う命題の真偽値
となり、lookingはpickを使って1番目の要素に対してkeep-lookingを適用する事になる。
keep-lookingの定義を使いlookingを評価してみる。
> (looking 'caviar '(6 2 4 caviar 5 7 3)) #t > (looking 'caviar '(6 2 grits caviar 5 7 3)) #f >
latの一部分に対して再帰しているのではないところです。
今までの再帰は基底部で必ず0か空リストになる様な呼び出しをしていた。リスト処理の場合はlatのcdrに対して再帰するので必ずいずれは空リストになる。ここではlatは再帰に際して変化していない。
関数値が定義されない引数が存在すると言う意味で部分関数と言っていると思われる。だたし既出の関数も引数に色々と前提があり全てが全関数だった訳ではないと思う。
eternity
何を引数に与えても無限に再帰し、関数値が確定しない。関数値が定義出来る引数が存在しなくても部分関数なのか?
eternityは第9章の後半で再登場する。