代替Y結合子の定義

Question

最近、私はYコンビネータの周りに頭を抱えていましたが、通常は以下のように定義されています（これはC＃ですが、選択する言語です）重要ではありません。

public delegate TResult SelfApplicable<TResult>(SelfApplicable<TResult> r); 

public static TResult U<TResult>(SelfApplicable<TResult> r) 
{ 
    return r(r); 
} 

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return U<Func<TArg1, TReturn>>(r => arg1 => f(U(r))(arg1)); 
} 

それは（しゃれが意図した）完全に機能的ですが、私の定義は非常に簡単であるように思わ：

public static Func<TArg1, TReturn> Y<TArg1, TReturn>(Func<Func<TArg1, TReturn>, Func<TArg1, TReturn>> f) 
{ 
    return f(n => Y(f)(n)); 
} 

なぜ後者何らかの理由があります定義それほど一般的ではありません（私はまだネット上でそれを見つける必要があります）？それはおそらくY自体を定義することと関係がありますか？

Answer 1

ハスケル・カリーは、次のように定義され、型なしラムダ計算に匿名の再帰関数を定義して使用するようにYコンビネータを発明：
Y = λf·(λx·f (x x)) (λx·f (x x))

をマイ定義はそれとして、Yコンビネータの本来の目的に反し再帰関数を定義するためのC＃の固有のサポートに依存しています。しかし、C＃で匿名の再帰関数を定義できるという点ではまだ有用です。

Answer 2

私はあなたの質問が何であるかはよく分からないが、私はYコンビネータやソリューションどちらも野生の多くを見ていることを理由は二つあると思います：

1. 無名再帰関数は本当にまれです。特に、C＃には末尾再帰のための大きなサポートがありません。 C＃で擬似「匿名」再帰ラムダを定義する方法より簡単に（初心者のためのより読み）あります

2. ：

   Func<int, int> fac = null; 
   fac = x => x == 0 ? 1 : fac(x - 1) * x; 
   

   は確かに、これは匿名ではないであるが、それは「十分に近い」です実用的な目的のために。

Answer 3

無名再帰、すなわち不動点コンビネータでは、しばしば不可欠で見られ、強く型付けされた言語、匿名を定義するよりも、あなたの[検閲]機能に名前を付けることが容易であるという非常に単純な理由のためにされていません同じタスクを実行する関数です。また、OOA & Dは、複数の場所に値を持つコードを複製するべきではないことを教えてくれます。共通の場所から名前を付ける必要があります。ラムダは本質的に1回限りです。ループ構造のようなより一般的なアルゴリズムで使用するための非常に状況依存のコードを数行指定する方法。ほとんどの再帰アルゴリズムは、一般的なアプリケーション（ソート、再帰的なシリーズ生成など）を持つもので、一般的にそれらをより広く利用できるようにします。

ラムダの計算を除いて、ほとんどのプログラミング言語では、無名関数Fは使用する前に存在しなければなりません。これは、それ自体の観点から関数の定義を排除します。

Fact(0) -> 1 

Fact(i) -> Fact(i-1) * i 

これはErlangの世界では、この除き、罰金のようになります。このようアーランなどいくつかの関数型言語では、関数Fは、簡単な関数をより複雑なもののためのベースケースとして使用されている「オーバーロード」を、使用して定義されています名前付きファンクション "ファクト"になりました。このメソッドを呼び出すと、パラメータが一致する最初のファンクションが見つかるまで、プログラムはオーバーロードを「落ちます」。 C＃では値に基づいてオーバーロードを選択することができないため、この正確な構文とC＃では同等のものはありません。

このトリックは、何らかの形で関数に渡すことのできる関数への参照を取得することです。いろいろな方法がありますが、いずれも既存の参考文献を必要とします。名前で関数を参照できない場合、FPコンビネータ関数のタイプはFunc<Func<Func<Func<Func<...です。 Konradの方法が最も簡単ですが、C＃ではハックが発生します（コンパイルされますが、ReSharperはInvalidOperationExceptionの可能性があると不平を言いますが、nullメソッドポインタは呼び出せません）。

ことはここでは基本的には、暗黙的に暗黙に型付けされたラムダを入力することができないため、デリゲートの回避策を使用して、私は単純な場合に使用する何か：

public static class YCombinator 
{ 
    public delegate TOut RLambda<TIn, TOut>(RLambda<TIn, TOut> rLambda, TIn a); 
    public static Func<T,T> Curry<T>(this RLambda<T,T> rLambda) 
    { 
     return a => rLambda(rLambda, a); 
    } 
} 

//usage 
var curriedLambda = YCombinator.Curry<int>((f, i) => i <= 0 ? 1 : f(f, i - 1)*i) 
var shouldBe120 = curriedLambda(5); 

あなたが入力タイプのケースを処理するためにCurry<TIn, TOut>過負荷を宣言することができます最初のN個の素数のリストを生成するなど、出力タイプではありません。その関数Pは、より小さな素数で割り切れないすべての正の整数のリストを生成する関数として再帰的に定義することができます。定点P（1）=> 2（ないとはいえ、非常に効率的なもの）再帰アルゴリズムを定義することができ、そこからベースケースを定義：

var curriedLambda = 
      YCombinator.Curry<int, List<int>>(
       (p, i) => i == 1 
           ? new List<int>{2} 
           : p(p, i - 1) 
            .Concat(new[] 
               { 
                Enumerable.Range(p(p, i - 1)[i - 2], 
                    int.MaxValue - p(p, i - 1)[i - 2]) 
                 .First(x => p(p, i - 1).All(y => x%y != 0)) 
               }).ToList() 
       ); 
     Assert.AreEqual(new []{2,3,5,7,11}, curriedLambda(5)); 

こうして難問は、それ自体を提示します。あなたは確かにすべてを高次関数として定義することができますが、この素数ファインダは、機能的にではなく命令的に定義すると、より高速になります。主なスピードアップは、各レベルでp（p、i-1）を定義するだけであり、再帰レベルごとに3回評価されません。機能的に働くように設計されたよりスマートな言語は、あなたのためにそれを行います。