朝食Yコンビネータ
Schemeで「階乗関数を次に与えるfix関数を用いて再帰を用いず書きなさい」という課題。
fixはこれ
(define (fix f) (lambda (x) ((f (fix f)) x)))
正直どうして良いものか見当もつかなかったので先人たちの知恵に頼ることに。
検索の結果次のページが役に立った。
よく見るとどちらもサークルの先輩だったので今度会ったらお礼を言わないと。
普通に階乗関数を書いた時の再帰処理の部分をYコンビネータに投げることで
自分の名前を再度呼び出す必要性を無くすということのようだ。
（とりあえずそういう風に解釈した）
なぜそんなことをする必要があるのか理解に苦しんだが決め手となったのはflatlineさんの次の一文である。
「これはfacという名前に頼って再帰を行っているのがけしからん！ たとえfacの定義本体をなすλ式だけを取り出そうとも機能するようにせよ」というのがコンビネータ理論の要求（？）なわけだ．
そういうことらしい。
しかも今回Yコンビネータとして使用しているfixはそれ自身が再帰している
いわば似非Yコンビネータだが、Yコンビネータも再帰を用いずに書ける（！）とのことだ。
そうすると全編通して再帰の出番が無くなるという凄いことに。
そこでふと思ったのだが、漸化式とYコンビネータがあれば再帰を用いずに
対象の式を記述できるのであれば、数学の時間に出てきた「一般項を求めるのが難しい漸化式」も
このロジックを用いれば一般項を返してくる関数を引き出せるのだろうか。
よくわからない。
とりあえず目下必要なのは課題である。
無事に完成したので載せておくことにする。
(define (fact n)
(define (pre-fac f)
(lambda (n)
(if (< n 1)
1
(* n (f (- n 1))))))
((fix pre-fac) n))
