不動点コンビネータ

ウィキペディア

不動点コンビネータ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/27 00:35 UTC 版)

「Yコンビネータ」は不動点演算子について説明しているこの項目へ転送されています。カリフォルニア州の企業については「Yコンビネータ (企業)」をご覧ください。

不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数 ${\displaystyle f}$

グラフ簡約（en:Graph reductionを参照）による計算系では、不動点コンビネータへの適用(apply, application)は理論通り展開しても良いが、左の図のように循環のあるグラフに簡約するという一種の、のぞき穴的最適化が知られている。また、これはカリーのYコンビネータではないが(この図のように)便宜的にYという名前で呼ばれていることもある^[7]。

関数の自己参照による無名再帰

詳細は「無名再帰」を参照

不動点コンビネータは識別子に束縛されていない関数が自分自身を呼び出す一般的な方法であるが、言語によっては特別な名前などで自分自身を呼び出すことができる。詳細は無名再帰を参照。

関連項目

• 不動点反復法
• 無名関数
• 固有関数

脚注

1. ^ This terminology appear to be largely folklore, but it does appear in the following:
   • Trey Nash, Accelerated C# 2008, Apress, 2007, ISBN 1590598733, p. 462--463. Derived substantially from Wes Dyer's blog (see next item).
   • Wes Dyer Anonymous Recursion in C#, February 02, 2007, contains a substantially similar example found in the book above, but accompanied by more discussion.
2. ^ The If Works Deriving the Y combinator, January 10th, 2008
3. ^ ^{a b} Goldberg, 2005
4. ^ Haskell mailing list thread on How to define Y combinator in Haskell, 15 Sep 2006
5. ^ The Y Combinator in Arc and Java - Javaコード
6. ^ bind - Fixed point combinators in C++ - Stack Overflow - C++コード
7. ^ たとえば、Turnerの"A New Implementation Technique for Applicative Languages"（doi:10.1002/spe.4380090105）の Figure. 3 と、その直前の説明を見よ。

参考文献

• Werner Kluge, Abstract computing machines: a lambda calculus perspective, Springer, 2005, ISBN 3540211462, pp. 73-77
• Mayer Goldberg, (2005) On the Recursive Enumerability of Fixed-Point Combinators, BRICS Report RS-05-1, University of Aarhus