대체 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를 정의하는 것과 관련이 있을까요?
Y = λf·(λx·f (x x)) (λx·f (x x))

내 정의는 그것으로 Y 연결자의 원래 목적을 패배 다음과 같이

Answer 1

하스켈 카레 정의, 정의하고 형식화되지 않은 람다 계산법에 익명 재귀 함수를 사용하는 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는 여러 곳에서 가치가있는 코드를 중복해서는 안됩니다. 그것은 지명되어야하며 공통의 장소에서 접근 가능해야합니다. 람다는 본질적으로 일회성이다. 루핑 구문과 같은보다 일반적인 알고리즘에서 사용하기위한 상황 별 코드 몇 줄을 지정하는 방법. 대부분의 재귀 알고리즘은 꽤 일반적인 응용 프로그램 (정렬, 재귀 계열 생성 등)을 사용하는 것으로, 일반적으로 더 널리 액세스 할 수있게합니다.

람다 미적분을 제외하고 익명의 함수 F가 있어야만 사용할 수 있습니다. 그것은 그 자체로 기능의 정의를 배제합니다.얼랑 세계이있는 것을 제외하고,

Fact(0) -> 1 

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

이 잘 될 것입니다 : 같은 얼랑 같은 일부 기능 언어에서 함수 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 번 평가되지 않습니다. 기능적으로 작동하도록 설계된 더 똑똑한 언어가 당신을 위해 그렇게 할 것입니다.