Ologの再起関数の例:階乗
下記のExample 6.6.1のOlogが面白かったのでメモ。
階乗のOlog
階乗のOlogをテキトーに翻訳して描いてみた。
(TikZで頑張る気力が出ないので、スライドでざっと描いている)
階乗を表していると言われてもぱっと見まったくわからない。
式変形を追わないと理解できそうにないので、とりあえず等式を抜き出す。
$${s; p = \text{id}_A}$$
$${s; q = d; f}$$
$${i_0; f = \omega}$$
$${i_1; f = s; m}$$
ただ、図式順のポイントフリースタイルは馴染みがないので、見慣れた形式に書き換える。
$${p(s(n)) = \text{id}_A(n)}$$
$${q(s(n)) = f(d(n))}$$
$${f(i_0(0)) = \omega(0)}$$
$${f(i_1(n)) = m(s(n))}$$
二つ組
射影$${p, q}$$、恒等写像$${\text{id}_A}$$の性質と式1, 2から、$${s}$$がどのような二つ組を作るかわかる。
$$
s(n) = ( \text{id}_A(n), f(d(n))) = (n, f(d(n)))
$$
場合分け
$${s}$$の式を式4と合わせておく。
$$
f(i_1(n)) = m(s(n)) = m(n, f(d(n)))
$$
さらに、直和に伴う包含写像$${i_0, i_1}$$の性質と式3から、次のように場合分けで書ける。
$$
f(n) = \left\{ \begin{array}{ll}
\omega(0) & \text{if} n = 0\\
m(n, f(d(n))) & \text{if} n \gt 0
\end{array} \right.
$$
残りの関数の選定
ここで、$${\omega, d, m}$$のそれぞれを、1への定数関数、前者関数、積とする。
$${\omega(0) = 1}$$
$${d(n) = n - 1}$$
$${m(x, y) = x \times y}$$
すると、$${f}$$は次のように書けて、確かに階乗になる。
$$
f(n) = \left\{ \begin{array}{ll}
1 & \text{if} n = 0\\
n \times f(n - 1) & \text{if} n \gt 0
\end{array} \right.
$$
実用性は感じないけど、パズルっぽくて面白い。
この記事が参加している募集
この記事が気に入ったらサポートをしてみませんか?