不動点コンビネータ
型無しラムダ計算における不動点コンビネータは無数に存在するので、特に珍しいわけではない。2005年、メイヤー・ゴールドバーグ (Mayer Goldberg) は型無しラムダ計算の不動点コンビネータの集合が帰納的可算集合であることを示した。
次のようないくつかの不動点コンビネータ(ジャン・ウィレム・クロップによって組み立てられた)は、主として遊びに使われる。
Yk = (L L L L L L L L L L L L L L L L L L L L L L L L L L)
ここで
L = λabcdefghijklmnopqstuvwxyzr. (r (t h i s i s a f i x e d p o i n t c o m b i n a t o r))
再帰データ型(システムFωを参照)をサポートしているプログラミング言語では、型レベルで再帰を適切に計算することによってYコンビネータの型付けが可能になる。変数xを自己適用する必要性は同型の (Rec a -> a) を用いて定義される型 (Rec a) によって管理することができる。
例として、以下のHaskellコードは、型とともに同型写像のInとoutの2つの方向の名前を持つ。
そして次のように書くことができる。
OCamlによる等価なコードは以下。