こんにちは、22Bのzer0-starです。普段はインターネットの治安を守るために魔法少女として活躍しています。同志募集中です。よろしくお願いします。

この記事はtraP夏のブログリレー14日目の記事です。

ところでみなさん

不動点ってご存知ですか？

ある関数$f$の不動点とは、$f(x)=x$となるような$x$のことです。すなわち、関数$f$を適用しても変わらない(不動な)値のことです。例えば、$f(x)=x^2$の不動点は$0$と$1$です。

また、関数$f$に対して$\mathrm{fix}(f)$が$f$の不動点を与える(すなわち$f(\mathrm{fix}(f))=\mathrm{fix}(f)$となる)ような$\mathrm{fix}$を不動点コンビネータと呼んだりします。

この記事では、プログラミングにおける不動点について見ていきたいと思います。

実装

不動点コンビネータをプログラム上で実装するには、いくつか方法があります。

再帰的定義

$f(\mathrm{fix}(f))=\mathrm{fix}(f)$という定義を素直に書き下せばいいです。

Haskellfix :: (a -> a) -> a
fix f = f (fix f)

ただし、正格評価の言語(Haskell以外の大抵の言語)では、上の定義は無限に止まらない再帰を引き起こします。$\eta$-変換したこちらの定義を使うと無限ループを回避できますが、関数 -> 関数の形の関数しか受け取ることができなくなります。(aを() -> aに変換すれば実質同じになりますが)

PureScriptfix :: forall a b. ((a -> b) -> a -> b) -> a -> b
fix f = f (\x -> fix f x)

Yコンビネータ・Zコンビネータ

Yコンビネータというものがあります。これは、$\lambda$計算における不動点コンビネータのひとつです。

$$Y=\lambda f.(\lambda x.f(xx))(\lambda x.f(xx))$$

名前による再帰を行っていないところが注目ポイントですね。ちなみに、$Yf$が実際に関数$f$の不動点を与えることを確認するのはそう難しくないので、やってみてはいかがでしょうか。

$\lambda$計算で考えられたYコンビネータですが、プログラムで実装することもできます。ただし、再帰的な型が必要になるので、強い型システムが無い静的型付け言語では普通に実装できないかもしれません。

Haskellnewtype Inf a = Inf (Inf a -> a)

-- NOINLINEを付けないとインライン展開が無限に続き、コンパイルに失敗する
{-# NOINLINE runInf #-}
runInf :: Inf a -> Inf a -> a
runInf (Inf f) = f

y :: (a -> a) -> a
y f = (\x -> f (runInf x x)) (Inf \x -> f (runInf x x))

Inf aは、自分自身を適用できる関数を表す型です(Infという名前は私が適当につけました)。展開すると、$((\cdots \to a)\to a)\to a$という無限に再帰するヤバい関数になります。

例によって正格評価の言語だと無限ループになるので、$\eta$-変換したバージョンのZコンビネータを使うと良いでしょう。

$$Z=\lambda f.(\lambda x.f(\lambda y.xxy))(\lambda x.f(\lambda y.xxy))$$

PureScriptnewtype Inf a = Inf (Inf a -> a)

runInf :: forall a. Inf a -> Inf a -> a
runInf (Inf f) = f

z :: forall a b. ((a -> b) -> (a -> b)) -> (a -> b)
z f = (\x -> f (\y -> runInf x x y)) (Inf \x -> f (\y -> runInf x x y))

Haskellparadox :: a
paradox = (\x -> (runInf x x)) (Inf \x -> (runInf x x))

応用(再帰)

再帰とは、不動点です。

再帰関数を実装する一般的な方法は、関数に名前を付けて自分自身の定義で自分の名前を使うことです。

F#// ML系言語ではletではなくlet recを使う必要がある
let rec fib n = if n <= 1 then n else fib (n - 1) + fib (n - 2)

しかし、不動点を利用することで名前による再帰を用いずに再帰をすることができます。

今、不動点コンビネータfixが与えられていたとします。すると、例えば上の例は次のように書き換えられます。

F#// 名前による再帰をしていないので、recが必要ない！
let fib = fix (fun f n -> if n <= 1 then n else f (n - 1) + f (n - 2))

一般に、let recはfixを用いてletに書き換えられます。

F#let rec hoge = ...
↓
let hoge = fix (fun hoge -> ...)

また、同じような流れ(ただし工夫は必要)で相互再帰も実現できるのですが、長くなってしまうので省きます。

というわけで

イカが

弟子

鷹！？

終わりです。楽しんでいただけましたか？

プログラミングにおける不動点という限定的なトピックなのに結構書けてびっくりしています。実は、もっと小ネタとかうんちくが出てくるんですが、小ネタすぎて記事の流れで出せないのでお蔵入りです。

割とがんばって書いたし満足しているんですが、不完全な記事が生成されることもあるので、間違いの指摘などは歓迎です。あと、わかりにくかったら言ってくださいね

以上、みんなのインターネット・魔法少女zer0-starでした。

明日の担当は@yashuさんです。楽し〜み