Alternatywna kombinacja Y definicji

Question

Spędziłem trochę czasu owijając moją głowę wokół kombinator Y ostatnio i odkryłem, że jest to zwykle zdefiniowane (mniej więcej) w następujący sposób (to jest w języku C#, ale jest to język wyboru nie ma znaczenia):

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

Mimo to doskonale funkcjonalne (gra słów nie przeznaczonych), wydaje się, że moja definicja jest znacznie prostsza:

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

Czy istnieje jakikolwiek powód, dlaczego ten ostatni definicja nie jest tak powszechny (muszę go jeszcze znaleźć w sieci)? Czy może miałoby to coś wspólnego z definiowaniem Y pod względem samej siebie?

Answer 1

Haskell Curry wynalazł COMBINATOR Y definiowania i wykorzystywania anonimowych funkcje rekurencyjne w bez typu rachunku lambda, zdefiniowane następująco:
Y = λf·(λx·f (x x)) (λx·f (x x))

Moja definicja pokonuje oryginalny cel combinator Y jak to polega na nieodłącznym wsparciu C# dla definiowania funkcji rekursywnych. Jest to jednak nadal przydatne, ponieważ pozwala zdefiniować anonimowe funkcje rekursywne w języku C#.

Answer 2

Nie jestem pewien, co jest Twoje pytanie, ale myślę, że powód ani syntezatora Y ani rozwiązanie są postrzegane dużo w środowisku naturalnym jest dwojaki:

1. anonimowe funkcje rekurencyjne są bardzo rzadkie; w szczególności, ponieważ C# nie ma wielkiego (czytaj: żadnego) wsparcia dla rekurencji ogona.

2. Jest to znacznie łatwiejsze (bardziej czytelne dla niewtajemniczonych) sposób definiowania pseudo- „anonimowy” rekurencyjnych lambdy w C#:

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

   przyznane, to nie anonimowy, ale to „wystarczająco blisko” do celów praktycznych.

Answer 3

Anonymous rekurencji, tzn ze operator paradoksalny, nie jest często postrzegany w charakterze, silnie typowanych języków, dla bardzo prostego powodu, że łatwiej jest wymienić swój [censored] funkcję niż zdefiniować anonimowy funkcja, która wykonuje to samo zadanie. Ponadto, OOA & D uczy nas, że kod, który ma wartość w wielu miejscach, nie powinien być duplikowany; powinien być nazwany, a zatem dostępny ze wspólnego miejsca. Lambdy z natury są jednorazowe; sposób określania kilku linii bardzo specyficznego dla sytuacji kodu do użycia w bardziej ogólnym algorytmie, takim jak konstrukcje pętli. Większość algorytmów rekursywnych to rzeczy, które mają dość ogólną aplikację (sortowanie, generowanie serii rekursywnych itp.), Co zazwyczaj prowadzi do tego, że stają się one bardziej dostępne.

Na marginesie, w większości języków programowania musi istnieć anonimowa funkcja F, zanim będzie można z niej korzystać. Wyklucza to definicję funkcji w sensie samym w sobie.W niektórych językach funkcyjnych, takich jak Erlang, funkcja F jest określona przy użyciu „przeciążenia”, gdzie prostsze funkcje są używane jako przypadkach bazowych dla bardziej złożonych:

Fact(0) -> 1 

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

To byłoby w porządku, poza tym, że w tym Erlang-świata jest teraz nazwaną funkcją "Fact", a podczas wywoływania tej metody program "upada" przez przeciążenia, dopóki nie znajdzie pierwszego, dla którego parametry pasują do siebie. Nie ma odpowiednika w C# do tej dokładnej konstrukcji, ponieważ C# nie obsługuje wyboru przeciążenia na podstawie wartości.

Sztuką jest jakoś uzyskać odniesienie do funkcji, która może być przekazana do funkcji. Istnieje wiele sposobów, z których wszystkie wymagają wcześniejszego odniesienia SOMEWHERE. Jeśli nie możesz odwoływać się do funkcji po nazwie, typem funkcji kombinatorowej FP jest Func<Func<Func<Func<Func<.... Metoda Konrada jest najłatwiejsza, ale w C# kończy się na hackowaniu (kompiluje się, ale ReSharper wciąż narzeka, że ​​jest to możliwe InvalidOperationException; nie może wywołać wskaźnika metody zerowej).

Oto coś mogę używać prostych przypadkach, w zasadzie za pomocą obejścia Delegat nie mogąc niejawnie wpisać niejawnie wpisany lambda:

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

Można zadeklarować Curry<TIn, TOut> przeciążenie do obsługi przypadki, gdy typ wejścia nie jest typem wyjściowym, takim jak tworzenie listy pierwszych N liczb pierwszych; tę funkcję P można rekurencyjnie zdefiniować jako funkcję, która tworzy listę wszystkich dodatnich liczb całkowitych, które nie są podzielne przez mniejszą liczbę pierwszą. Stały punkt P (1) => 2 tworzy obudowę podstawy, z której rekurencyjny algorytm może być określony (aczkolwiek nie jest bardzo wydajnym)

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

W ten sposób prezentuje się dylemat; chociaż z całą pewnością MOŻESZ zdefiniować wszystko jako funkcję wyższego rzędu, ten główny celownik będzie DUŻO szybszy, jeśli zostanie zdefiniowany imperatywnie zamiast funkcjonalnie. Głównym przyspieszeniem jest po prostu zdefiniowanie p (p, i-1) na każdym poziomie, więc nie jest ono oceniane 3 razy na poziomie rekursji. Mądrzejszy język zaprojektowany do działania funkcjonalnie zrobiłby to za Ciebie.