FANDOM


とりあえずメモです。有益な結論の出ているエントリではありません。

\(f(x) = 2x\) という関数 \(f\) があった場合、ラムダ計算では関数の名前 \(f\) を消して \(\lambda x. 2x\) と書きます。ラムダ計算では関数の引数が常に 1 つなので、多変数関数の場合、「1 つの引数」を取り、「残りの引数をとる関数」を返す関数に変換します。これがカリー化です。

ここで、任意の関数 \(g\) をカリー化することを \(curry(g)\) と書くことにします。例えば \(g(x, y) = x^y\) という関数をカリー化したものは、\(curry(g) = \lambda x. (\lambda y. x^y)\) となります。

重要なのは、カリー化した関数を単に呼び出した場合に出てくる関数がどういったものであるかです。\(g(x, y) = x^y\) をカリー化したものに引数として \(3\) を与えると \(curry(g)(3) = h(y) = \lambda y. 3^y\) となります。ここで自由変数 \(x\) が \(h(y)\) において \(3\) に束縛されています。つまり、元の \(g(x, y)\) の \(x\) に \(3\) を部分適用した関数 \(h(y)\) を定義したことになります。

このカリー化を導入することで、Wikipedia におけるハイパー演算子の定義

\begin{align} hyper\ n(a, b) &= a^{(n)}b \\ &= \begin{cases} b+1, & \mbox{if }n=0 \\ a, & \mbox{if }n=1,b=0 \\ 0, & \mbox{if }n=2,b=0 \\ 1, & \mbox{if }n\ge 3,b=0 \\ a ^ {(n-1)} ( a ^ {(n)} (b - 1)) & \mbox{otherwise} \end{cases} \end{align}

この形から

\begin{align} hyper\ n(a, b) &= a^{(n)}b \\ &= f_n(a, b) \\ &= \begin{cases} b+1, & \mbox{if }n=0 \\ curry(f_0)(a)^b(a), & \mbox{if }n=1 \\ curry(f_{n-1})(a)^{b-1}(a) & \mbox{otherwise} \end{cases} \end{align}

という形で書くことができるようになります。

ここから、前回のエントリに書いた通り原始帰納関数を数え上げる形にできないかと模索していたのですが、このアプローチを発展させても煩雑な形にしかならないと思い、また本質的に必要なものではないのでやめました。一応、\(f_n\) の定義を、\(f_{n-1}\) をカリー化した関数から出てきた関数の羃の形にはできていますが……。

しかし、ラムダ計算と束縛によって複雑な関数を簡潔な形にできる場合もあるので、もしかしたら別のことで使えるかも知れません。ラムダ計算について学んだついでのメモとして残しておきます。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki