不動点コンビネータ

不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x) = xを満たすようなxのことをいう。 すなわち高階関数g が不動点コンビネータであるとは、 任意の関数f に対し、p = g(f)とすると, f(p) = p が成立する 事を指す。 不動点コンビネータの定義は、任意の関数f に対し、 が成立する事であるとも言い換えられる。 第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。 不動点コンビネータは高階関数であるため、その歴史はラムダ計算の発達と深く関係している。型無しラムダ計算（英: untyped lambda calculus）においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。