[functional-programming] Y- 콤비 네이터 란 무엇입니까? [닫은]

Y- 콤비 네이터는 “기능”(다른 기능에서 작동하는 기능)으로, 그 자체에서 함수를 참조 할 수 없을 때 재귀를 가능하게합니다. 컴퓨터 과학 이론에서는 재귀를 일반화 하고 구현을 추상화함으로써 문제의 기능의 실제 작업과 분리합니다. 재귀 함수에 컴파일 타임 이름이 필요하지 않은 이점은 일종의 보너스입니다. =)

람다 함수 를 지원하는 언어로 적용 할 수 있습니다 . 표현람다 기반 특성은 일반적으로 이름으로 자신을 참조 할 수 없음을 의미합니다. 그리고 변수를 선언하고 참조한 다음 람다를 할당하여 자체 참조 루프를 완성하는 방식 으로이 문제를 해결하는 것은 쉽지 않습니다. 람다 변수를 복사하고 원래 변수를 다시 할당하면 자체 참조가 중단됩니다.

Y- 콤비 네이터는 정적 유형 언어 ( 프로 시 저럴 언어가 자주 사용됨)에서 구현하고 사용하기에 번거 롭습니다. 일반적으로 입력 제한 사항은 문제가되는 함수가 컴파일시 알려지기 위해 인수의 수가 필요하기 때문입니다. 즉, y- 콤비 네이터를 사용해야하는 인수 개수에 대해 작성해야합니다.

아래는 C #에서 Y-Combinator의 사용법과 작동 방식의 예입니다.

Y- 콤비 네이터를 사용하는 것은 재귀 함수를 구성하는 “비정상적인”방법을 포함합니다. 먼저 함수 자체보다는 기존 함수를 호출하는 코드 조각으로 함수를 작성해야합니다.

// Factorial, if func does the same thing as this bit of code...
x == 0 ? 1: x * func(x - 1);

그런 다음 함수를 호출하는 함수로 바꾸고 그렇게하는 함수를 반환합니다. 하나의 기능을 사용하고 다른 기능을 수행하는 작업을 수행하기 때문에 기능이라고합니다.

// A function that creates a factorial, but only if you pass in
// a function that does what the inner function is doing.
Func<Func<Double, Double>, Func<Double, Double>> fact =
  (recurs) =>
    (x) =>
      x == 0 ? 1 : x * recurs(x - 1);

이제 함수를 가져 와서 계승처럼 보이는 다른 함수를 반환하지만 자체 호출하는 대신 외부 함수에 전달 된 인수를 호출하는 함수가 있습니다. 이것을 계승으로 만드는 방법은 무엇입니까? 내부 함수를 자체로 전달하십시오. Y-Combinator는 영구 이름을 가진 함수이므로 재귀를 유발할 수 있습니다.

// One-argument Y-Combinator.
public static Func<T, TResult> Y<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> F)
{
  return
    t =>  // A function that...
      F(  // Calls the factorial creator, passing in...
        Y(F)  // The result of this same Y-combinator function call...
              // (Here is where the recursion is introduced.)
        )
      (t); // And passes the argument into the work function.
}

계승 호출 자체보다는 계승이 계승 생성기 (Y-Combinator에 대한 재귀 호출에 의해 리턴 됨)를 호출합니다. 그리고 t의 현재 값에 따라 생성기에서 반환 된 함수는 t-1로 생성기를 다시 호출하거나 1을 반환하여 재귀를 종료합니다.

복잡하고 비밀 스럽지만 모두 런타임에 흔들리며 작동의 핵심은 “지연된 실행”과 두 기능에 걸친 재귀의 분리입니다. 내부 F는 인수로 전달되어 필요한 경우에만 다음 반복에서 호출됩니다 .

답변

// Here's the function that we want to recurse.
X = function (recurse, n) {
  if (0 == n)
    return 1;
  else
    return n * recurse(recurse, n - 1);
};

// This will get X to recurse.
Y = function (builder, n) {
  return builder(builder, n);
};

// Here it is in action.
Y(
  X,
  5
);

// No assignment this time.
function (builder, n) {
  return builder(builder, n);
}(
  function (recurse, n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse, n - 1);
  },
  5
);

// Original
F = function (i, j) {
  ...
};
F(i,j);

// Transformed
F = function (i) { return function (j) {
  ...
}};
F(i)(j);

// The dreaded Y-combinator in action!
function (builder) { return function (n) {
  return builder(builder)(n);
}}(
  function (recurse) { return function (n) {
    if (0 == n)
      return 1;
    else
      return n * recurse(recurse)(n - 1);
  }})(
  5
);

function factorial(n) {
    return n == 0 ? 1 : n * factorial(n - 1);
}

function fact() {
    return function(n) {
        return n == 0 ? 1 : n * fact()(n - 1);
    };
}

var factorial = fact();

function fact(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
}

function recurser(x) {
    return fact(recurser)(x);
}

var factorial = fact(recurser);

function recurser(f) {
    return fact(function(x) {
        return f(f)(x);
    });
}

var factorial = recurser(recurser);

function Y() {
    return (function(f) {
        return f(f);
    })(recurser);
}

var factorial = Y();

function Y() {
    return (function(f) {
        return f(f);
    })(function(f) {
        return fact(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y();

function Y(le) {
    return (function(f) {
        return f(f);
    })(function(f) {
        return le(function(x) {
            return f(f)(x);
        });
    });
}

var factorial = Y(function(recurse) {
    return function(n) {
        return n == 0 ? 1 : n * recurse(n - 1);
    };
});

var Y = function(f) {
  return (function(g) {
    return g(g);
  })(function(h) {
    return function() {
      return f(h(h)).apply(null, arguments);
    };
  });
};

var factorial = Y(function(recurse) {
  return function(x) {
    return x == 0 ? 1 : x * recurse(x-1);
  };
});

factorial(5)  // -> 120