不動点コンビネータで無名再帰を作る流れをおさらい

どうも、趣味で関数型言語を書いている者です。
長らく関数型言語やってなかったら無名再帰を忘れかけていたので、おさらいがてら不動点コンビネータで無名再帰を作る流れを書き下します。

以下、Haskell の文法で書かれたコードをもとに説明していきます。

<br>

## 無名再帰とは？

まずはモチベーションの確認から。
通常、再帰関数は、

```haskell
sum :: Num a => [a] -> a
sum []     = 0
sum (x:xs) = x + sum xs
```

といったように、関数定義の中で自分自身を呼ぶことで再帰処理を記述できます。
この例では、 `sum (x:xs) = x + sum xs` の部分で自分自身を呼んでいますね。

では、

- 関数に名前を付けることができない (無名関数しかない)
- 関数定義の中で自分自身を呼ぶことができない

というような制限プレイの中で再帰をしたくなったらどうすればいいでしょうか？
そんな要望に応えるために人類は **無名再帰** という方法を編み出しました。その名の通り、関数名に依らない再帰処理の方法です。

今回は無名再帰の具体的な作り方を見ていきます。

<br>

## 不動点コンビネータ (Y コンビネータ)

いきなりですが **不動点コンビネータ** というやつがあります。
形式的な定義はこうです。

```haskell
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)) ...))))
```

というように延々と関数の呼び出しが繰り返されます。
この **関数の呼び出しが延々と繰り返される** というやつは、多くの言語の多くの状況で実際にやってみると **処理が無限にループして停止しない** という扱いになるでしょう。

そんな関数が役に立つのか？  
大丈夫、話はもう少しだけ続きます。

<br>

## 引数を消去する関数を与えてみる

今度は `fix` に **引数を消去する関数** を与えてみましょう。
例えば、定数関数 `const` を持ち出して、

```haskell
const :: a -> b -> a
const x _ = x
```

`const 0` を `fix` に与えてみます。

```
fix (const 0)
=> const 0 (fix (const 0))
=> 0
```

というわけで、式は `0` に評価されて停止しました。
このように `fix` に与える引数によっては無事に停止して値を返すことがあるのです。

無限ループに陥らずにちゃんと値を返してくれるのは、遅延評価戦略の言語では **関数の展開はその結果が本当に必要とされる時まで行われない** からですね。 **とっても Lazy** なんです。
`const` に渡された第二引数は計算結果に必要が無いため、評価も展開もされずに捨てられます。それがたとえ `fix g` であっても。

<br>

## 複数の引数を与えてみる

ここまでで、

- 不動点コンビネータ は関数の呼び出しを延々繰り返すような動作をすること
- 引数を消去する関数を渡せば停止させることもできること

を見ました。

再帰処理らしいことをしようとしたら **特定の条件で終了させる** ということをしたくなるはずです。
では、終了条件を表現する前段階として複数の引数を渡してみましょう。

`fix` に次のような `g` と `n` を渡します。

```haskell
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` に渡されることが分かりました。
と同時に、 `g` には `(fix g)` も渡されるので `(fix g)` を消去することもできていますね。

`fix` を1変数関数として見ていたときには使いどころが分かりづらかったのが、 **何か実用的な式を組み立てられそうな気がしてきた** と思いませんか？

<br>

## 実用的な計算例: 階乗計算

いよいよ不動点コンビネータを使った実用的な例を見ていきましょう。
0以上の自然数 n の階乗 `fact n` [^2] を計算してみましょう。

階乗関数 `fact` を定義するための補助関数 `fact'` を次のように定義します。

```haskell
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` を計算することができました。
つまり、

```haskell
fact :: Integer -> Integer
fact = fix fact'
```

として階乗関数 `fact` を定義することができました。

<br>

## 何が起こっている？

あらためて `fact'` と `fact` の定義を見てみましょう。

```haskell
fact' next n = if n == 0 then 1 else n * next (n - 1)

fact = fix fact'
-- fact n = fix fact' n と書いても良い
```

`fact'` の定義にも `fact` の定義にも自分自身を呼び出す記述はありませんから、今回のテーマ通り **自分自身を呼び出すことなく再帰処理を実現できた** ということになります。
さらに `fact'` の定義をよく見ていると仮引数の `next` をまるで再帰呼び出しのように使っていることが分かります。

形式的な知識としてはこうです。

- `fix` に関数 `g` を与えることで関数 `f` が得られる
- `f` は `g` よりも引数が一つ少ない関数として振る舞う
- `g` の第一仮引数 `next` の呼び出しは、`f` の再帰呼び出しのように振る舞う

掴めてきましたか？実際に紙に手書きで運算してみるとより理解が深まるかも知れません。

<br>

## 一般化してみる

せっかく関数型言語という **抽象的な道具** を持ち出しているのでもっと一般化しましょう。
一般の再帰処理に必要な要素は以下のようなものです、

- `cond` : 再帰の終了条件
- `process` : 再帰呼び出し時の計算処理
- `initial` : 再帰呼び出し時の初期値

これらが与えられたとき、不動点コンビネータを用いた再帰処理は以下のように作られます。

```haskell
g next n = if cond n then initial
                     else process next n

f = fix g
```

ちなみに先ほどの階乗関数の場合、

```haskell
cond = (== 0)
process = \next n -> n * next (n - 1)
initial = 1
```

です。

さらに `cond`, `process`, `initial` の組から `g` を作る関数 `h` を考えてみると、

```haskell
h cond process initial = \next x ->
    if cond x
        then initial
        else process next x
```

となります。

`f`, `g`, `h` を一気にまとめると、
`cond`, `process`, `initial` の組が与えられたとき、対応する再帰処理を実現する関数 `f` は、

```haskell
f = fix $ \next x ->
    if cond x
        then initial
        else process next x
```

と書けることが分かります。

<br>

## 実際に REPL で試す

ここまで書いてきたことは、実際に動く Haskell プログラムに落とし込むこともできます。
実際に無名再帰を使ってリストの総和を求める `mySum` を定義してみました。

https://repl.it/@todays_mitsui/SpryIdleTheory

こいつ、動くぞ！

<br>

はい、

<br>

## おわりに

というわけで不動点コンビネータ `fix` を使って無名再帰を実現する方法について書いてきました。

ちなみにこの記事は [型無しラムダ計算インタプリタ Mogul 言語](https://mogul-lang.mudatobunka.org/) で『無名再帰でも書くかー』と思ってみたものの無名再帰の書き方をすっかり忘れていたため、思い出しがてら書かれました。
コンビネータ理論を確立してくれた先人に感謝します。

<br>

私からは以上です。

[^1]: Haskell では `Control.Monad.Fix` モジュールを import することで実際に `fix` を使えるようになります
[^2]: 形式的な定義で `fact n = n * (n - 1) * (n -2 ) * ... * 2 * 1` という計算です