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