Scheme手習い(14) 部分関数と全関数
第9章「……もう一度、もう一度、もう一度、……」は、変な関数の話？
まずは部分関数と全関数から
(define looking
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
(define keep-looking
(lambda (a sorn lat)
(cond ((number? sorn) (keep-looking a (pick sorn lat) lat))
(else (eq? a sorn)))))この関数、引数によっては無限ループに入ってしまい、実行が終わりません
つまり関数が値を返しません
引数によっては関数が値を返さない関数を部分関数と言います
これまで出てきた関数は、リストを扱うものであれば
リストのcdr（や場合によってはcar）について再帰を行っていました
そのため、再帰のたびにリストの長さが短くなるので
いつかは関数の実行が終わることが保証されていました
つまりどんな引数を与えても関数は値を返していました
そのような関数を全関数と言います
普通に関数と言ったらたいてい全関数だと思います
ただし、「どんな引数を」といっても「定義域の中では」という条件がつきます
この本では定義域、つまり「正しい」引数が何かについては書いてないことが多いです
読めばわかるだろ的な
正しくない引数だったら無限ループになるような関数はもしかするとあったかもしれませんが
たぶんエラーが出て終わるか知らんぷりして変な値を返すかどちらかだったと思われます
エラーが出て終わるのと、無限ループになって値を持たないというのとはたぶん扱いが異なるんでしょう
keep-lookingはリストを扱う関数ですが、再帰のときlatをそのまま再帰しています
そのためいつかは完了するという保証は（ぱっと見）ありませんし
実際無限ループになることがあるので部分関数です
そういう再帰を「不自然な再帰」と呼んでます
eternityはどんな引数を与えても無限ループになる、「最も」部分的な関数です
(define eternity (lambda (x) (eternity x)))別にただ無限ループするだけの関数に引数なんていらないんじゃという気がしなくもないんですが
なにか背景があるんでしょう
引数がなかったら関数じゃなくて定数みたいなものですし
次はalignという関数
(define shift
(lambda (pair)
(build (first (first pair))
(build (second (first pair)) (second pair)))))
(define align
(lambda (para)
(cond
((atom? para) para)
((a-pair? (first para)) (align (shift para)))
(else (build (first para) (align (second para)))))))でこの関数が何なのかというと、再帰時に引数が小さくなっているわけではないので
さてこれは全関数なのでしょうか、すぐにはわかりません、ということ
そもそも何をやっているかわかりにくいです
引数の第一要素がペアだったら、第一要素の第二要素をとっぱらって
第二要素のほうにくっつける、というのを繰り返しています
と言ってもやっぱりわかりにくいので具体例で調べてみます
(((1 (2 (3 4))) 5) (((6 7) 8) 9))
((1 (2 (3 4))) (5 (((6 7) 8) 9)))
(1 ((2 (3 4)) (5 (((6 7) 8) 9))))
(1 (2 ((3 4) (5 (((6 7) 8) 9)))))
(1 (2 (3 (4 (5 (((6 7) 8) 9))))))
(1 (2 (3 (4 (5 ((6 7) (8 9)))))))
(1 (2 (3 (4 (5 (6 (7 (8 9))))))))正確にはうまく言えないけれど、だんだん右に寄っていく感じです
なんかいつかは終わりそうな雰囲気ですね
定義域は(例によって)書いてありませんがソースから逆算すると
アトムとかアトムのペアとかペアのペアとかそういうもののようです
引数のparaってなんの略？パラメータのこと？とかなり悩んだんですが
あとでporaというのが出てくるんで調べてみたらparaは誤植のようです
Pair OR Atomってことでしょう
というあたりもヒントになって
ちゃんと書けばこういうこと
- アトムは pora である
- pora と pora のペアは pora である
（例によって）特に説明もなく話は進んでいきます
微妙に暗示されてはいるんですが
alignの引数中のアトムの数を数える関数を書けますか。
書けますけどそれが何か？
(define length*
(lambda (para)
(cond ((atom? para) 1)
(else (o+ (length* (first para))
(length* (second para)))))))狙いはわからなくても先へ進みます
alignへの引数とその再帰的な使用で変化しているものがほかにありますか。
はい、あります。ペアの第1の要素はより簡単になっていますが、第2の要素はより複雑になっています。
引数の長さを決めるのにlength*は間違った関数ではないでしょうか。
文字通りに取れば間違ってはいないと思いますが
alignが全関数であることを説明しようとしているっぽいので
その目的にはそぐわないということらしいです
もっと良い関数を見つけられますか。
もっと良い関数では、第1要素にもっと注意を払わなければいけません。
注意を払うってなんですか
次のweight*のようなものでしょうか。
(define weight* (lambda (pora) (cond ((atom? pora) 1) (else (o+ (o* (weight* (first para)) 2) (weight* (second para)))))))これは良さそうに見えます。
重みをつけるってことでした
alignが全関数、つまり必ず値を返すってことを証明しようという流れのようです
length*はshiftしても変わらないので役に立ちませんが、
weight*ならペアの第1の要素が簡単になれば小さくなっていきそうです
処理が進むにつれて小さくなるけれども、いくらでも小さくなれるわけではないので
どこかで止まるはず、ってことかな
n要素のporaの場合、
(weight* pora)の値がlength*より小さくはならないことは明らかですが
最小値はたぶん 2n-1 になるはず
ついでに最大値は 2^n-1
ちょっとweight*の減り方を見てみます
引数のweight*を表示するようにして・・・そういえば表示ってどうやるんだっけ
こうか
(define align
(lambda (para)
(display (format "~a~%" (weight* para)))
(cond
((atom? para) para)
((a-pair? (first para)) (align (shift para)))
(else (build (first para) (align (second para)))))))実行
> (align '(((1 (2 (3 4))) 5) (((6 7) 8) 9)))
45
31
29
27
25
23
21
19
17
15
9
7
5
3
1
(1 (2 (3 (4 (5 (6 (7 (8 9))))))))そうじゃない
そうか、全体のweight*を知りたいのに関数に渡されるのはcarとかcdrとかだけですからね
だめだな
アイデアもないので真心で手間ひまかけて解決
> (weight* '(((1 (2 (3 4))) 5) (((6 7) 8) 9)))
45
> (weight* '((1 (2 (3 4))) (5 (((6 7) 8) 9))))
31
> (weight* '(1 ((2 (3 4)) (5 (((6 7) 8) 9)))))
29
> (weight* '(1 (2 ((3 4) (5 (((6 7) 8) 9))))))
27
> (weight* '(1 (2 (3 (4 (5 (((6 7) 8) 9)))))))
25
> (weight* '(1 (2 (3 (4 (5 ((6 7) (8 9))))))))
19
> (weight* '(1 (2 (3 (4 (5 (6 (7 (8 9)))))))))
172n - 1で止まりました
それっぽい感じです
いやでもほんとかな
単調減少といっても増えることはないというだけで、減らないこともあって
必ず止まるとは言い切れないのかも？
最小値があるのは間違いないけど、最小値に達したら必ず止まると言えるかな？
condの条件に沿って考えてみます
- poraがアトムであれば終わる
- weight*は1
これはいい
- poraの第1要素がペアであれば、poraをshiftしてまたalignする
このときは小さくなるでしょうか
例を作って考えてみます
A、B、Cをpora型の値(Aはペア)として
まずは( (A B) C)をshiftして(A (B C))にします
(weight* X)はちょっと長いので n(X) と書くことにして
n( ( (A B) C)) = 4n(A)+2n(B)+n(C)で、n( (A (B C))) = 2n(A)+2n(B)+n(C)
n(A) > 1だから( (A B) C)をshiftすると必ずweight*は減少しますね
ここまではいいとして
それをalignしたときつまり(align (shift (A (B C))))のweight*はどうでしょう
(align (A (B C)))と同じか、より小さければいいんですが
alignの中ではshiftしかしてないから、増えることはないだろう、とか？
いや、それが確かかどうかわからないから細かく見ていこうとしているんでした
ここは置いておいて先に進んでみます
- poraの第1要素がペアでなければ（つまりアトムならば）、第二要素をalignする
第一要素のアトムをaと書くことにすると
n( (a (B C)))=2*1+2n(B)+n(C)で、n( (a (align (B C)))) はええと・・・
n( (B C))とn(align(B C))の関係がわからないとやっぱり進みません
結局n(X) > n(align(X))がわからないとなんとも言えないですね
って元に戻ってるじゃないかよ
これはもっと細かく考えないとダメな気がします
数学的帰納法っぽく考えてみたらどうでしょうか
簡単なporaから順番に証明していく方針で
アトムから始めてbuildで作っていったものがporaですから
- 集合S(1)をアトム全体の集合とし、その要素をs(1)と書く
ここがスタート
- 集合S(2)は、S(1)の要素でできたペア全体の集合とし、その要素をs(2)と書く
1回buildしました
- 集合S(3)は、S(1)またはS(2)の要素でできたペア全体の集合とし、その要素をs(3)と書く
2回buildしました
- 集合S(n)は、S(1)〜S(n-1)の要素でできたペア全体の集合とし、その要素をs(n)と書く
(n - 1)回buildしました
でS(n)を全部の自然数について集めればpora全体の集合になります
そうすると、(first s(k)) ∈ S(k - 1)、(second s(k)) ∈ S(k - 1) のはず
S(1)については成り立つ、S(k-1)までが成り立てばS(k)も成り立つ、って感じで
それでできちゃうとweight*を作った意味がなくなるかな？
まあやってみます
- n = 1 のとき、つまり pora ∈ S(1) のとき
(align pora) = pora となり停止する - n = k - 1 のとき
といく前に n = 2 のとき、つまり pora ∈ S(2) のときで考えてみます
結城浩先生も例示は理解の試金石とおっしゃってますからね
難しくなる前にまず
- (first pora)がアトムならば
(align pora) = (build (first pora) (align (second pora)))
(first pora)= poraであり、(second pora) ∈ S(1) だから停止する - (first pora)がペアならば
(align pora) = (align (shift pora))
あーだめかー
(shift pora) ∈ S(2)だもんなー
不自然な再帰だからなー
ってわかってみるとあたりまえだなー
なんでやる前に気づかないかなー
そこでweight*の出番？
(weight* pora)で数学的帰納法？
いいのかなあとびとびだったりしますが
- (weight* pora) = 1 のとき、
poraはひとつのアトムだから、(align pora)は停止する - (weight* pora) < k のとき(align pora)が停止すると仮定して
(weight* pora) = k となる pora について考える
- (first pora)がアトムならば
(align pora) = (build (first pora) (align (second pora)))
(weight* (second pora)) は明らかに (weight* pora) = k より小さいから
(align (second pora))は停止する
したがって(align pora)も停止する - (first pora)がペアならば
(align pora) = (align (shift pora))
上で（雑に）書いたとおり、shiftすると必ずweight*は減少するから
(weight* (shift pora)) < (weight* pora) = k
したがって(align pora)は停止する
- (first pora)がアトムならば
お、できた？
一応理屈は通ってる気がします
weight*エライ？
ちょっと修正したshuffleという関数
(define shuffle
(lambda (pora)
(cond ((atom? pora) pora)
((a-pair? (first pora)) (shuffle (revpair pora)))
(else (build (first pora)
(shuffle (second pora)))))))これはさらにどういう結果を返すのかわかりにくいですが
簡単に無限ループに入るので部分関数です
