どうも、趣味で関数型言語を書いている者です。
長らく関数型言語やってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。
以下、Haskell の文法で書かれたコードをもとに説明していきます。
無名再帰とは？
まずはモチベーションの確認から。
通常、再帰関数は、
sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs
といったように、関数定義の中で自分自身を呼ぶことで再帰処理を記述できます。
この例では、 sum (x:xs) = x + sum xs の部分で自分自身を呼んでいますね。
では、以下のような制約をイメージしてみてください。
- 関数に名前を付けることができない
- 関数定義の中で自分自身を呼ぶことができない
このような制限の中で再帰を書きたくなったらどうすればいいでしょうか？
そんな要望に応えるために人類は 無名再帰 という方法を編み出しました。その名の通り、関数名に依らない再帰処理の方法です。
今回は無名再帰の具体的な作り方を見ていきます。
不動点コンビネータ (Y コンビネータ)
いきなりですが 不動点コンビネータ というやつがあります。
形式的な定義はこうです。
fix :: (a -> a) -> a
fix g = g (fix g)
見ての通り、関数 g を引数に取り、自分自身 fix g を引数として g を呼び出します。
ちょっと何がしたいのか分からない感じの関数ですね。では実際にこの fix に引数を与えた式を運算してみましょう。1
fix g
=> g (fix g)
=> g (g (fix g))
=> g (g (g (fix g)))
=> g (g (g (g (fix g))))
...
=> g (g (g (g (... (g (fix g)) ...))))
というように延々と関数の呼び出しが繰り返されます。
この 関数の呼び出しが延々と繰り返される というやつは、多くの言語の多くの状況で実際にやってみると 処理が無限にループして停止しない という扱いになるでしょう。
そんな関数が役に立つのか？
大丈夫、話はもう少しだけ続きます。
引数を消去する関数を与えてみる
今度は fix に 引数を消去する関数 を与えてみましょう。
例えば、定数関数 const を持ち出して、
const :: a -> b -> a
const x _ = x
const 0 を fix に与えてみます。
fix (const 0)
=> const 0 (fix (const 0))
=> 0
というわけで、式は 0 に評価されて停止しました。
このように fix に与える引数によっては無事に停止して値を返すことがあるのです。
これは Haskell をはじめとする遅延評価戦略の言語では 関数の展開はその結果が必要とされるまで行われない からですね。 とっても Lazy なんです。
const に渡された第二引数は計算結果に必要無いため評価も展開もされずに捨てられます。それがたとえ fix g であっても。
複数の引数を与えてみる
ここまでで、
- 不動点コンビネータ は関数の呼び出しを延々繰り返すような動作をすること
- 引数を消去する関数を渡せば停止させることもできること
を見ました。
再帰処理らしいことをしようとしたら 特定の条件で終了させる ということをしたくなるはずです。
では、終了条件を表現する前段階として複数の引数を渡してみましょう。
fix に次のような g と n を渡します。
g _ n = if n == 0 then 0 else 1
n = 42
すると fix g n は次のように運算されます、
fix g n
=> g (fix g) 42
=> if 42 == 0 then 0 else 1
=> 1
はい、というわけで。fix に2つ以上の引数を渡すと2つめ以降の引数は g に渡されることが分かりました。
fix を1変数関数として見ていたときには使いどころが分かりづらかったのが、 何か実用的な式を組み立てられそうな気がしてきた と思いませんか？
実用的な計算例: 階乗計算
いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 fact n 2 を計算してみましょう。
階乗関数 fact を定義するための補助関数 fact' を次のように定義します。
fact' next n = if n == 0 then 1 else n * next (n - 1)
これを fix に与えて運算してみましょう。
fix fact' n
=> fact' (fix fact') n
=> if n == 0 then 1 else n * fix fact' (n - 1)
はい！ else 節に注目してください fix fact' (n - 1) という形で再帰的構造が見えていますね。
n にも具体的な値を入れてみましょう。 fix fact' 3 を運算します。
fix fact' 3
-- fix の定義に従い fix fact' を展開
=> fact' (fix fact') 3
-- fact' の定義に従いfact' (fix fact') 3 を展開
=> if 3 == 0 then 1 else 3 * fix fact' (3 - 1)
-- 条件に従って if 式を評価
=> 3 * fix fact' (3 - 1)
=> 3 * fix fact' 2
-- 以下、繰り返し
=> 3 * fact' (fix fact') 2
=> 3 * (if 2 == 0 then 1 else 2 * fix fact' (2 - 1))
=> 3 * 2 * fix fact' (2 - 1)
=> 3 * 2 * fix fact' 1
=> 3 * 2 * fact' (fix fact') 1
=> 3 * 2 * (if 1 == 0 then 1 else 1 * fix fact' (1 - 1))
=> 3 * 2 * 1 * fix fact' (1 - 1)
=> 3 * 2 * 1 * fix fact' 0
=> 3 * 2 * 1 * fact' (fix fact') 0
=> 3 * 2 * 1 * (if 0 == 0 then 1 else 0 * fix fact' (1 - 1))
=> 3 * 2 * 1 * 1
=> 6
このように fix fact' 3 によって fact 3 を計算することができました。
つまり、
fact n = fix fact' n
として階乗関数 fact を定義することができました。
何が起こっている？
あらためて fact' と fact の定義を見てみましょう。
fact' next n = if n == 0 then 1 else n * next (n - 1)
fact n = fix fact' n
fact' の定義にも fact の定義にも自分自身を呼び出す記述はありませんから、今回のテーマ通り 自分自身を呼び出すことなく再帰処理を実現できた ということになります。
さらに fact' の定義をよく見ていると仮引数の next をまるで再帰呼び出しのように使っていることが分かります。
形式的な知識としてはこうです。
fix に関数 g を与えることで関数 f が得られるf は g よりも引数が一つ少ない関数として振る舞うg の第一仮引数 next の呼び出しは、f の再帰呼び出しのように振る舞う
掴めてきましたか？実際に紙に手書きで運算してみるとより理解が深まるかも知れません。
一般化してみる
せっかく関数型言語という 抽象的な道具 を持ち出しているのでもっと一般化しましょう。
一般の再帰処理に必要な要素は以下のようなものです、
cond : 再帰の終了条件process : 再帰呼び出し時の計算処理initial : 再帰呼び出し時の初期値
これらが与えられたとき、不動点コンビネータを用いた再帰処理は以下のように作られます。
g next n = if cond n then initial
else process next n
f = fix g
ちなみに先ほどの階乗関数の場合、
cond = (== 0)
process = \next n -> n * next (n - 1)
initial = 1
です。
さらに cond, process, initial の組から g を作る関数 h を考えてみると、
h cond process initial = \next x ->
if cond x
then initial
else process next x
となります。
f, g, h を一気にまとめると、
cond, process, initial の組が与えられたとき、対応する再帰処理を実現する関数 f は、
f = fix $ \next x ->
if cond x
then initial
else process next x
と書けることが分かります。
実際に REPL で試す
ここまで書いてきたことは、実際に動く Haskell プログラムに落とし込むこともできます。
実際に無名再帰を使ってリストの総和を求める mySum を定義してみました。
こいつ、動くぞ！
はい、
まとめ
というわけで不動点コンビネータ fix を使って無名再帰を実現する方法について書いてきました。
ちなみにこの記事は 型無しラムダ計算インタプリタ Mogul 言語 で『無名再帰でも書くかー』と思ってみたものの無名再帰の書き方をすっかり忘れていたため、思い出しがてら書かれました。
コンビネータ理論を確立してくれた先人に感謝します。
私からは以上です。
