Y # birleştiriciyi C# dinamik kullanarak uyguladım ve eğer yapmadıysam, nedir?

Question

Beynim mazoşistik modda görünüyor, bu nedenle this, this ve this'da boğulduktan sonra, C# içindeki bazı DIY'lerle uğraşmak istedim.

ben Y-combinator sanmıyorum aşağıda, ile geldi, ama kendisine referans almadan, bir özyinesiz fonksiyon özyinelemeli yapmak yönetmek gözüküyor:

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

Yani bunlar verilmiş:

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); 

Biz bu oluşturabilir:

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))); 

,

Answer 1

Hayır, bu Y birleştiricisi değil; Orada sadece yarı yoldasın. Kendi uygulamanızı, uyguladığınız "tohum" işlevleri içinde hesaba katmanız gerekiyor. Bu, bunun yerine, şudur: bu olmalıdır

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); 

Not ilk tanımı iki oluşum aksine ikinci tanımı self tek oluşumu.

(the one often called Z, not Y

(:) ayrıntılı tekrar düzenlenebilir eklemek için :) BTW, C# kullanmanızın çağrı değer-ile-değerlendirmeyle lambda taşı taklit beri düzenlenen, sabit nokta istediğiniz combinator edilir

Y g = g (Y g) 

Ama işlevini aramadan önce en pratik programlama dillerinde, bir fonksiyonun argümanı değerlendirmek: Y açıklanır denklem bu (derivasyon için the wikipedia page bakınız). Programlama dilleri topluluğunda, buna çağrı-değer değerlendirmesi denir (C/C++/Fortran/etc programcılarının "çağrıya göre" vs "çağrıya göre ara" ya da "kopyala geri al" ile karşılaştırmasıyla karıştırılmaması gerekir. , vb).

Ama eğer bunu yaparsak, biz ise

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

, biz özyinelemeli fonksiyon inşa zamanımızın tüm harcama ve uygulayarak etrafında varamazdik iyi olur.

Ad-by-değerlendirmede, diğer yandan, burada, (Y g), değerlendirilmemiş argüman ifadesine bir işlev, burada g uygularsınız. Ancak, g, fact gibi ise, herhangi bir şey yapmadan önce başka bir argümanı bekliyor. Bu yüzden (Y g)'u değerlendirmeye çalışmadan önce ikinci argümanı g'a bekleyeceğiz --- ve fonksiyonun ne olduğuna bağlı olarak (yani, bir temel durumu varsa), (Y g)'u değerlendirmeye gerek duymayabiliriz. Bu nedenle, Y, ad-sora değerlendirme için çalışıyor.

Arama değeri için düzeltme, denklemi değiştirmektir.. Yerine Y g = g (Y g) nedeniyle, yerine aşağıdaki denklemde gibi bir şey istiyorum:

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

(Ben doğru doğru ya da yakın denklemi var düşünüyorum Sen bunu hesaplamak ve Z tanımına uygun olup olmadığını görebilirsiniz.

Bunu düşünmenin bir yolu, "tüm özyinelemeli işlevi" hesaplamak ve onu g'a vermek yerine, bir seferde özyinelemeyi birazcık hesaplayacak bir işlevi elden geçiririz --- ve yalnızca Aslında biraz daha fazlasına ihtiyacımız var, bu yüzden onu bir argümana uygulayabiliriz (x).