不動点コンビネータ

定義

不動点

$ f(x)=xを満たすような$ xのこと。

不動点コンビネータ

与えられた関数の不動点を求める高階関数のこと。

任意の関数$ fに対し、$ p=y(f)とすると、$ f(p)=pが成立する。このとき、$ yは不動点コンビネータ

$ f(y(f))=y(f)を満たすような$ yとも言い換えられる

これは、$ f(f(f(f(f(y(f))))))=y(f)ような計算式も満たすことができる$ yとも考えられる。ここで、何度$ fに入力しても出力が変わらないことから、$ yのことを不動点というようだ。

何ができるか？

識別子に束縛されない関数の再帰、すなわち無名再帰が実現できる。らしい。

code:.hs

-- Yコンビネータは、すぐに定義できる

yCombinator f = f (yCombinator f)

-- Haskellでsumがやりたい場合の再帰方法は...

mySum :: (Num a) => a -> a

mySum [] = 0

mySum (x:xs) = x + mySum xs

-- Yコンビネータを利用する場合

main = do

print $ yCombinator (\f (x:xs) -> case xs of [] -> x

_ -> x + f xs) 1,2,3

-- これも同様

-- つまり、yCombinator f = f (yCombinator f) なので、それに list を渡すと、ラムダ式が以下の２つの引数をとる

-- f (yCombinator f) 1,2,3

-- あとは、ラムダ式の内部が実行されるだけ。f xsはyCombinator f xsと同様なので、また同様にラムダ式が実行される

main = do

print $ (yCombinator (\f (x:xs) -> case xs of [] -> x

_ -> x + f xs)) 1,2,3

-- ポイントは、yCombinator の展開が遅延評価されること

-- yCombinator が遅延評価されると、f を導出することができる

-- これにより、何度も f を取り出し、再帰を実現することができる