不動点コンビネータ
fixed point combinator
不動点演算子とも言う
与えられた関数の不動点を求める関数(コンビネータ)
不動点コンビネータgに対して以下が成り立つ
任意の関数fに対し、
p = g(f)とすると、
f(p) = pが成立する
これは以下のように言い換えられる
任意の関数fに対し、f(g(f)) = g(f)が成り立つ
上の説明におけるpが不動点である
要するに、任意の関数fを不動点コンビネータに適用することで、不動点が求められる
例
Yコンビネータ
無名関数で再帰を行っている
Zコンビネータ
チューリング不動点コンビネータ
fix関数
参考
不動点コンビネータ - Wikipedia
不動点コンビネータにより再帰を実現できることの証明
いくつかの不動点コンビネータの例
https://docs.google.com/presentation/d/1UJneVe12RZtoiCtmnzXgkpxPr-wDCoqxcNES29ZrxzE/edit#slide=id.p