14

私の脳は自虐モードにあるようで、これ、これ、およびこれに溺れた後、C＃でDIYをいじりたいと思っていました。

私はYコンビネーターではないと思いますが、それ自体を参照せずに、非再帰関数を再帰的にすることができたようです:

Func<Func<dynamic, dynamic>, Func<dynamic, dynamic>> Y = x => x(x);

したがって、これらを考えると：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);
Func<dynamic, Func<dynamic, dynamic>> fib = 
                  self => n => n < 2 ? n : self(self)(n-1) + self(self)(n-2);

これらを生成できます。

Func<dynamic, dynamic> Fact = Y(fact);
Func<dynamic, dynamic> Fib = Y(fib);

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fact({0})={1}", i, Fact(i)));

Enumerable.Range(0, 10)
          .ToList()
          .ForEach(i => Console.WriteLine("Fib({0})={1}", i, Fib(i)));
4

1 に答える 1

7

いいえ、それは Y コンビネータではありません。あなたはまだ道半ばです。適用先の「シード」関数内で自己適用を除外する必要があります。つまり、これの代わりに:

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(self)(n - 1);

あなたはこれを持っている必要があります：

Func<dynamic, Func<dynamic, dynamic>> fact = 
                  self => n => n == 0 ? 1 : n * self(n - 1);

self最初の定義では が 2 回出現するのに対し、2 番目の定義では が1 回出現することに注意してください。

(追加するために編集:) ところで、C# の使用は値による呼び出しの評価でラムダ計算をシミュレートするため、必要な固定小数点コンビネーターは、Y ではなく Z と呼ばれることが多いものです。

(詳しく説明するために再度編集:) 説明する方程式は次のとおりです (導出Yについてはウィキペディアのページを参照してください)。

Y g = g (Y g)

しかし、ほとんどの実用的なプログラミング言語では、関数を呼び出す前に関数の引数を評価します。プログラミング言語コミュニティでは、これは値による呼び出し評価と呼ばれます (C/C++/Fortran/etc プログラマーが「値による呼び出し」と「参照による呼び出し」と「コピー復元による呼び出し」を区別する方法と混同しないでください)。など）。

しかし、それを行うと、

Y g = g (Y g) = g (g (Y g)) = g (g (g (Y g))) = ...

つまり、再帰関数の作成にすべての時間を費やし、それを適用することは決してありません。

一方、名前による呼び出しの評価では、関数 heregを未評価の引数式here に適用します(Y g)。しかし、のgような場合はfact、何かを行う前に別の引数を待っています。したがって、さらにg評価を試みる前にの 2 番目の引数を待ちます(Y g)。また、関数が何をするか (つまり、基本ケースがある場合) によっては(Y g)、まったく評価する必要がない場合もあります。Yこれが、名前による呼び出しの評価で機能する理由です。

値渡しの修正は、式を変更することです。の代わりにY g = g (Y g)、代わりに次の式のようなものが必要です。

Z g = g (λx. (Z g) x)

(方程式は正しいか、ほぼ正しいと思います。計算して、 の定義に適合するかどうかを確認してくださいZ。)

これを考える1つの方法は、「再帰関数全体」を計算して に渡す代わりにg、再帰関数を少しずつ計算する関数を渡すことです---実際にもう少し必要な場合にのみそれを引数に適用できるようにします（x）。

于 2011-10-06T06:11:58.877 に答える