前回は、「defineできない関数が存在するみたいだねー。アハハ」って感じで終わったけど、
defineって何だろう？
再帰的な定義って何だろう？
って話題は続いていく。
これ以降、defineせずにリストの長さを求める再帰関数を作る過程を述べている模様。
長さ0のリストの長さを求める関数はこんなん。以降、関数名にセンスが無いのはご愛敬。
(define length0_0 (lambda (l) (cond ((null? l) 0) (else (+ 1 (eternity (cdr l)))))))
eternityの定義はid:yagiey:20080323を参照されたし。
んで、長さ1以下のリストの長さを求める関数は以下のように書ける。
(define length1_0 (lambda (l) (cond ((null? l) 0) (else (+ 1 (length0_0 (cdr l)))))))
同様に、長さ2以下のリストの長さを求める関数は以下のようにかける。
(define length2_0 (lambda (l) (cond ((null? l) 0) (else (+ 1 (length1_0 (cdr l)))))))
しかし今は「defineしないでリストの長さを求める再帰関数を作る」ってのが目的。
名前付きのlength**関数を使わずに書こうとしているわけだから、length1とlength2はそれぞれ次のように書きなおせる。
(define length1_1 (lambda (l) (cond ((null? l) 0) (else (+ 1 ((lambda (l) (cond ((null? l) 0) (else (+ 1 (eternity (cdr l)))))) (cdr l))))))) (define length2_1 (lambda (l) (cond ((null? l) 0) (else (+ 1 ((lambda (l) (cond ((null? l) 0) (else (+ 1 ((lambda (l) (cond ((null? l) 0) (else (+ 1 (eternity (cdr l)))))) (cdr l)))))) (cdr l)))))))
名前の部分を単純にlambda式で置き換えただけ。
gosh> ((lambda (n) (+ n 1)) 0) 1
みたいな感じで、即席で関数作って評価している感じかな。
このlambda式の部分がでっかくて読むのが大変だけど。
命令型言語やってると関数には名前があるもんだって思いがちだよね。
（最近では命令型言語でもlambda式を使えるようになってきてるねー。）
ここでlength1_1とlength2_1をよく眺めてみると、コードの中に同じようなパターンが含まれているのに気づく。
だもんで、第9の掟「共通するパターンを新しい関数に置き変えるべし」に倣い、新しい関数で書き直してみよう、と。
(define length0_2 ((lambda (f) (lambda (l) (cond ((null? l) 0) (else (+ 1 (f (cdr l))))))) eternity)) (define length1_2 ((lambda (f) (lambda (l) (cond ((null? l) 0) (else (+ 1 (f (cdr l))))))) ((lambda (g) (lambda (l) (cond ((null? l) 0) (else (+ 1 (g (cdr l))))))) eternity))) (define length2_2 ((lambda (f) (lambda (l) (cond ((null? l) 0) (else (+ 1 (f (cdr l))))))) ((lambda (g) (lambda (l) (cond ((null? l) 0) (else (+ 1 (g (cdr l))))))) ((lambda (h) (lambda (l) (cond ((null? l) 0) (else (+ 1 (h (cdr l))))))) eternity))))
lambdaの前で開くカッコが2個あるところで「関数を引数に取り関数を返す関数」を無名で作って、その場で引数を渡して関数を取り出してる感じ？
無名の関数作ってその場で評価、ってのはさっきも出てきたパターンだけど、高階関数になるとまた一段とムズいな。
んで、自分は
- length0_2がlength1_2のどこに使われているか
- length1_2がlength2_2のどこに使われているか
に注意して読んでみると見えてｷﾀ━━━━━━(ﾟ∀ﾟ)━━━━━━ !!!!!
あと、再帰の構造が見えやすくなって(・∀・)ｲｲ!!ね。
