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

Question

Y-combinator는 사물의 "기능적" 측면에서 본 컴퓨터 과학 개념입니다.대부분의 프로그래머는 결합자에 대해 들어본 적이 있어도 그것에 대해 전혀 알지 못합니다.

• Y-콤비네이터란 무엇입니까?
• 결합자는 어떻게 작동하나요?
• 그것들은 무엇에 좋은가요?
• 절차적 언어에 유용합니까?

Answer 1

오랫동안 읽을 준비가 되셨다면, 마이크 바니어(Mike Vanier)는 엄청난 설명.간단히 말해서, 기본적으로 반드시 지원하지 않는 언어로 재귀를 구현할 수 있습니다.

Answer 2

Y-combinator는 자체 내부에서 함수를 참조할 수 없을 때 재귀를 가능하게 하는 "기능적"(다른 함수에서 작동하는 함수)입니다.컴퓨터 과학 이론에서는 재귀를 일반화합니다, 구현을 추상화하여 해당 기능의 실제 작업과 분리합니다.재귀 함수에 대해 컴파일 타임 이름이 필요하지 않다는 이점은 일종의 보너스입니다.=)

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

Y-콤비네이터는 구현하기가 번거롭고 종종 사용하기도 합니다. 정적 유형 언어(이것은 절차적 언어 종종 그렇습니다), 일반적으로 입력 제한으로 인해 문제의 함수에 대한 인수 수가 컴파일 타임에 알려져야 하기 때문입니다.이는 사용해야 하는 모든 인수 수에 대해 y-combinator를 작성해야 함을 의미합니다.

다음은 C#에서 Y-Combinator를 사용하고 작동하는 방법에 대한 예입니다.

Y-combinator를 사용하면 재귀 함수를 구성하는 "비정상적인" 방법이 포함됩니다.먼저 함수 자체가 아닌 기존 함수를 호출하는 코드 조각으로 함수를 작성해야 합니다.

// 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는 인수로 통과됨, 다음 반복에서 호출됩니다. 필요한 경우에만.

Answer 3

나는 이것을 들어올렸다 http://www.mail-archive.com/boston-pm@mail.pm.org/msg02716.html 이것은 제가 몇 년 전에 쓴 설명입니다.

이 예에서는 JavaScript를 사용하지만 다른 많은 언어도 작동할 것입니다.

우리의 목표는 1 변수의 함수와 할당 없음, 이름별로 정의 등을 사용하여 1 변수의 재귀 함수를 작성할 수 있다는 것입니다.(이것이 우리의 목표 인 이유는 또 다른 질문입니다. 이것을 우리가주는 도전으로 받아들이자.) 불가능 해 보인다.예를 들어, Factorial을 구현합시다.

1 단계는 우리가 조금 속이면 쉽게 할 수 있다고 말하는 것입니다.2 변수의 함수와 할당을 사용하여 재귀를 설정하기 위해 과제를 사용하지 않아도됩니다.

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

이제 우리가 덜 속일 수 있는지 살펴보겠습니다.먼저 우리는 과제를 사용하고 있지만 필요하지 않습니다.우리는 단지 x와 y 인라인을 쓸 수 있습니다.

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

그러나 우리는 2 변수의 함수를 사용하여 1 변수의 함수를 얻습니다.문제를 해결할 수 있나요?Haskell Curry라는 이름의 똑똑한 사람은 깔끔한 트릭을 가지고 있습니다. 고차 기능이 양호하면 1 변수의 함수 만 필요합니다.증거는 2 (또는 일반적인 경우) 변수의 함수에서 순수한 기계적 텍스트 변환으로 1 변수로 얻을 수 있다는 것입니다.

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

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

어디 ...정확히 동일하게 유지됩니다.(이 트릭은 발명가 후에 "카레 링"이라고합니다.언어 Haskell은 Haskell Curry의 이름을 따서 명명되었습니다.쓸모없는 퀴즈 아래에 파일을 파일.) 이제 모든 곳 에서이 변환을 적용하면 최종 버전을 얻습니다.

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

자유롭게 시도해 보세요.return()을 반환하면 버튼에 연결합니다.이 코드는 2 개의 변수의 과제, 선언 또는 함수를 사용하지 않고 재귀 적으로 계승을 계산합니다.(그러나 그것이 어떻게 작동하는지 추적하는 것은 머리를 돌릴 수 있습니다.그리고 도출하지 않고 약간의 재구성을 건네 주면, 단지 약간의 재구성이 생겨날 수있는 코드가 생성됩니다.)

요인을 재귀 적으로 정의하는 4 줄을 원하는 다른 재귀 함수로 바꿀 수 있습니다.

Answer 4

처음부터 이것을 구축하려고 시도하면 어떤 소용이 있는지 궁금합니다.어디 보자.다음은 기본 재귀 계승 함수입니다.

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

리팩터링하고 다음과 같은 새 함수를 만들어 보겠습니다. fact 계산 자체를 수행하는 대신 익명의 계승 계산 함수를 반환합니다.

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

var factorial = fact();

좀 이상하긴 하지만 별 문제는 없습니다.우리는 각 단계에서 새로운 계승 함수를 생성하고 있습니다.

이 단계의 재귀는 여전히 매우 명확합니다.그만큼 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);

그거 좋은데, 하지만 recurser 여전히 자신의 이름을 알아야 합니다.이것도 매개변수화해 보겠습니다.

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

var factorial = recurser(recurser);

이제 전화보다는 recurser(recurser) 직접 결과를 반환하는 래퍼 함수를 ​​만들어 보겠습니다.

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

var factorial = Y();

이제 우리는 recurser 아예 이름을;이는 Y의 내부 함수에 대한 인수일 뿐이며 함수 자체로 대체될 수 있습니다.

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

var factorial = Y();

여전히 참조되는 유일한 외부 이름은 다음과 같습니다. fact, 하지만 이제 이 역시 쉽게 매개변수화되어 완전하고 일반적인 솔루션을 생성할 수 있다는 것이 분명해졌습니다.

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

Answer 5

위 답변의 대부분은 Y-combinator가 무엇인지 설명합니다. ~이다 하지만 그게 뭔지는 아니야 ~을 위한.

고정 소수점 결합기 것을 보여주기 위해 사용됩니다. 람다 미적분학 ~이다 튜링 완료.이는 계산이론에 있어 매우 중요한 결과이며, 함수형 프로그래밍.

고정 소수점 결합자를 공부한 것은 함수형 프로그래밍을 이해하는 데에도 도움이 되었습니다.하지만 실제 프로그래밍에서는 이러한 용도를 찾지 못했습니다.

Answer 6

y 조합자 자바스크립트:

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

편집하다:나는 코드를 보면서 많은 것을 배우지만, 이것은 배경 지식 없이는 이해하기가 약간 어렵습니다. 죄송합니다.다른 답변에서 제시된 몇 가지 일반적인 지식을 통해 무슨 일이 일어나고 있는지 분석할 수 있습니다.

Y 함수는 "y-결합자"입니다.이제 다음을 살펴보세요. var factorial Y가 사용되는 줄.매개변수가 있는 함수를 전달합니다(이 예에서는 recurse) 이는 나중에 내부 함수에서도 사용됩니다.매개변수 이름은 기본적으로 재귀 호출을 수행할 수 있는 내부 함수의 이름이 됩니다. recurse() 정의에 나와 있습니다.) y-combinator는 익명의 내부 함수를 Y에 전달된 함수의 매개 변수 이름과 연결하는 마법을 수행합니다.

Y가 마법을 수행하는 방법에 대한 자세한 설명은 다음을 확인하세요. 링크된 기사 (내가 아니라 btw.)

Answer 7

함수형 프로그래밍을 깊이 있게 접해본 적이 없고 지금 시작하고 싶지 않지만 약간 호기심이 있는 프로그래머를 위한:

Y 조합자는 함수에 이름이 없지만 인수로 전달되고, 반환 값으로 사용되며, 다른 함수 내에서 정의될 수 있는 상황에서 재귀를 구현할 수 있는 공식입니다.

함수를 인수로 자신에게 전달하여 작동하므로 자신을 호출할 수 있습니다.

이는 실제로 수학이지만 사실상 프로그래밍 언어인 람다 미적분학의 일부이며, 컴퓨터 과학, 특히 함수형 프로그래밍의 기본입니다.

프로그래밍 언어에서는 함수 이름을 지정할 수 있는 경향이 있기 때문에 Y 조합기의 일상적인 실용적인 가치는 제한되어 있습니다.

경찰 라인업에서 이를 식별해야 하는 경우 다음과 같습니다.

Y = λf.(λx.f(x x)) (λx.f(x x))

반복되는 내용으로 인해 쉽게 발견할 수 있습니다. (λx.f (x x)).

그만큼 λ 기호는 그리스 문자 람다로, 람다 미적분학에 이름을 부여합니다. (λx.t) 스타일 용어는 그것이 람다 미적분학의 모습이기 때문입니다.

Answer 8

다른 답변은 한 가지 중요한 사실 없이 이에 대한 매우 간결한 답변을 제공합니다.이렇게 복잡한 방식으로 실제 언어에서 고정 소수점 결합기를 구현할 필요가 없으며 이렇게 하면 실용적인 목적도 제공되지 않습니다("보세요, Y-combinator가 무엇인지 알고 있습니다" 제외).중요한 이론적 개념이지만 실제적인 가치는 거의 없습니다.

Answer 9

다음은 Y-Combinator 및 Factorial 함수의 JavaScript 구현입니다(Douglas Crockford의 기사에서 볼 수 있음: http://javascript.crockford.com/little.html).

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

var factorial = Y(function (fac) {
    return function (n) {
        return n <= 2 ? n : n * fac(n - 1);
    };
});

var number120 = factorial(5);

Answer 10

Y-Combinator는 플럭스 커패시터의 또 다른 이름입니다.

Answer 11

저는 Clojure와 Scheme 모두에서 Y-Combinator에 대한 일종의 "바보 가이드"를 작성하여 이를 이해하는 데 도움을 주었습니다.그들은 "The Little Schemer"의 자료에 영향을 받았습니다.

계획에서:https://gist.github.com/z5h/238891

또는 클로저:https://gist.github.com/z5h/5102747

두 튜토리얼 모두 주석이 포함된 코드이며 즐겨 사용하는 편집기에 잘라내어 붙여넣을 수 있어야 합니다.

Answer 12

익명 재귀

고정 소수점 결합자는 고차 함수입니다. fix 이는 정의에 따라 동등성을 충족합니다.

forall f.  fix f  =  f (fix f)

fix f 솔루션을 나타냅니다 x 고정 소수점 방정식

               x  =  f x

자연수의 계승은 다음과 같이 증명될 수 있습니다.

fact 0 = 1
fact n = n * fact (n - 1)

사용 fix, 일반/μ-재귀 함수에 대한 임의의 구성 증명은 익명의 자기 참조 없이 파생될 수 있습니다.

fact n = (fix fact') n

어디

fact' rec n = if n == 0
                then 1
                else n * rec (n - 1)

그렇게

   fact 3
=  (fix fact') 3
=  fact' (fix fact') 3
=  if 3 == 0 then 1 else 3 * (fix fact') (3 - 1)
=  3 * (fix fact') 2
=  3 * fact' (fix fact') 2
=  3 * if 2 == 0 then 1 else 2 * (fix fact') (2 - 1)
=  3 * 2 * (fix fact') 1
=  3 * 2 * fact' (fix fact') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (fix fact') (1 - 1)
=  3 * 2 * 1 * (fix fact') 0
=  3 * 2 * 1 * fact' (fix fact') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (fix fact') (0 - 1)
=  3 * 2 * 1 * 1
=  6

이 공식적인 증거는

fact 3  =  6

고정 소수점 결합기 동등성을 체계적으로 사용합니다. 다시 작성

fix fact'  ->  fact' (fix fact')

람다 미적분학

그만큼 형식화되지 않은 람다 미적분학 형식주의는 문맥에 구애받지 않는 문법으로 구성됩니다.

E ::= v        Variable
   |  λ v. E   Abstraction
   |  E E      Application

어디 v 변수에 대한 범위와 함께 베타 그리고 에타 감소 규칙

(λ x. B) E  ->  B[x := E]                                 Beta
  λ x. E x  ->  E          if x doesn’t occur free in E   Eta

베타 감소는 변수의 모든 무료 발생을 대체합니다. x 추상화("함수") 본문에서 B 표현(“인수”)으로 E.에타 감소는 중복 추상화를 제거합니다.형식상 생략되는 경우도 있다.안 줄일 수 없는 축소 규칙이 적용되지 않는 표현식은 정상 또는 정식 형식.

λ x y. E

는 약칭이다

λ x. λ y. E

(추상화 다중성),

E F G

는 약칭이다

(E F) G

(애플리케이션 왼쪽 연관성),

λ x. x

그리고

λ y. y

~이다 알파에 해당하는.

추상화와 응용은 람다 미적분학의 두 가지 유일한 "언어 기본 요소"이지만 다음을 허용합니다. 부호화 임의로 복잡한 데이터 및 작업을 수행합니다.

교회 숫자는 페아노 공리 자연수와 유사한 자연수를 인코딩한 것입니다.

   0  =  λ f x. x                 No application
   1  =  λ f x. f x               One application
   2  =  λ f x. f (f x)           Twofold
   3  =  λ f x. f (f (f x))       Threefold
    . . .

SUCC  =  λ n f x. f (n f x)       Successor
 ADD  =  λ n m f x. n f (m f x)   Addition
MULT  =  λ n m f x. n (m f) x     Multiplication
    . . .

공식적인 증거는

1 + 2  =  3

베타 감소 재작성 규칙 사용:

   ADD                      1            2
=  (λ n m f x. n f (m f x)) (λ g y. g y) (λ h z. h (h z))
=  (λ m f x. (λ g y. g y) f (m f x)) (λ h z. h (h z))
=  (λ m f x. (λ y. f y) (m f x)) (λ h z. h (h z))
=  (λ m f x. f (m f x)) (λ h z. h (h z))
=  λ f x. f ((λ h z. h (h z)) f x)
=  λ f x. f ((λ z. f (f z)) x)
=  λ f x. f (f (f x))                                       Normal form
=  3

결합자

람다 계산에서, 결합자 자유 변수를 포함하지 않는 추상화입니다.가장 간단하게: I, 신원 조합자

λ x. x

항등 함수와 동형

id x = x

이러한 결합자는 다음의 기본 연산자입니다. 조합기 미적분학 SKI 시스템처럼 말이죠.

S  =  λ x y z. x z (y z)
K  =  λ x y. x
I  =  λ x. x

베타 감소는 그렇지 않습니다. 강력하게 정규화 중;모든 축소 가능한 표현인 "redexes"가 베타 축소 하에서 정규 형식으로 수렴되는 것은 아닙니다.간단한 예는 오메가의 다양한 적용입니다. ω 결합자

λ x. x x

자신에게:

   (λ x. x x) (λ y. y y)
=  (λ y. y y) (λ y. y y)
. . .
=  _|_                     Bottom

가장 왼쪽 하위 표현식("머리")을 줄이는 것이 우선순위입니다. 적용순서 대체하기 전에 인수를 정규화합니다. 정상적인 순서 하지 않습니다.두 가지 전략은 열정적 평가와 유사합니다.C 및 게으른 평가(예:하스켈.

   K          (I a)        (ω ω)
=  (λ k l. k) ((λ i. i) a) ((λ x. x x) (λ y. y y))

열렬한 적용 순서 베타 감소에 따라 분기됩니다.

=  (λ k l. k) a ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ y. y y) (λ y. y y))
. . .
=  _|_

이후 엄격한 의미론

forall f.  f _|_  =  _|_

그러나 게으른 정상 순서 베타 감소에서는 수렴됩니다.

=  (λ l. ((λ i. i) a)) ((λ x. x x) (λ y. y y))
=  (λ l. a) ((λ x. x x) (λ y. y y))
=  a

표현식이 정규 형식을 가지면 정규 순서 베타 축소가 해당 표현식을 찾습니다.

와이

의 필수 속성은 Y 고정 소수점 결합기

λ f. (λ x. f (x x)) (λ x. f (x x))

에 의해 주어진다

   Y g
=  (λ f. (λ x. f (x x)) (λ x. f (x x))) g
=  (λ x. g (x x)) (λ x. g (x x))           =  Y g
=  g ((λ x. g (x x)) (λ x. g (x x)))       =  g (Y g)
=  g (g ((λ x. g (x x)) (λ x. g (x x))))   =  g (g (Y g))
. . .                                      . . .

동등성

Y g  =  g (Y g)

와 동형이다

fix f  =  f (fix f)

형식화되지 않은 람다 미적분학은 일반/μ-재귀 함수에 대한 임의의 구성 증명을 인코딩할 수 있습니다.

 FACT  =  λ n. Y FACT' n
FACT'  =  λ rec n. if n == 0 then 1 else n * rec (n - 1)

   FACT 3
=  (λ n. Y FACT' n) 3
=  Y FACT' 3
=  FACT' (Y FACT') 3
=  if 3 == 0 then 1 else 3 * (Y FACT') (3 - 1)
=  3 * (Y FACT') (3 - 1)
=  3 * FACT' (Y FACT') 2
=  3 * if 2 == 0 then 1 else 2 * (Y FACT') (2 - 1)
=  3 * 2 * (Y FACT') 1
=  3 * 2 * FACT' (Y FACT') 1
=  3 * 2 * if 1 == 0 then 1 else 1 * (Y FACT') (1 - 1)
=  3 * 2 * 1 * (Y FACT') 0
=  3 * 2 * 1 * FACT' (Y FACT') 0
=  3 * 2 * 1 * if 0 == 0 then 1 else 0 * (Y FACT') (0 - 1)
=  3 * 2 * 1 * 1
=  6

(곱셈 지연, 합류)

Churchian의 형식화되지 않은 람다 미적분학의 경우, 그 외에도 재귀적으로 열거 가능한 무한대의 고정 소수점 결합자가 존재하는 것으로 나타났습니다. Y.

 X  =  λ f. (λ x. x x) (λ x. f (x x))
Y'  =  (λ x y. x y x) (λ y x. y (x y x))
 Z  =  λ f. (λ x. f (λ v. x x v)) (λ x. f (λ v. x x v))
 Θ  =  (λ x y. y (x x y)) (λ x y. y (x x y))
  . . .

정규 순서 베타 감소는 확장되지 않은 유형화되지 않은 람다 미적분학을 Turing-complete 재작성 시스템으로 만듭니다.

Haskell에서는 고정 소수점 결합자를 우아하게 구현할 수 있습니다.

fix :: forall t. (t -> t) -> t
fix f = f (fix f)

Haskell의 게으름은 모든 하위 표현이 평가되기 전에 유한성으로 정규화됩니다.

primes :: Integral t => [t]
primes = sieve [2 ..]
   where
      sieve = fix (\ rec (p : ns) ->
                     p : rec [n | n <- ns
                                , n `rem` p /= 0])

---

• 데이비드 터너: 교회의 논문과 기능적 프로그래밍
• 알론조 교회: 초등정수론의 풀리지 않는 문제
• 람다 미적분학
• 교회-로서 정리

Answer 13

y-combinator는 익명 재귀를 구현합니다.그래서 대신

function fib( n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

넌 할 수있어

function ( fib, n ){ if( n<=1 ) return n; else return fib(n-1)+fib(n-2) }

물론 y-combinator는 call-by-name 언어에서만 작동합니다.이것을 일반적인 값별 호출 언어에서 사용하려면 관련 z-combinator가 필요합니다(y-combinator는 분기/무한 루프임).

Answer 14

콤비네이터의 초보자로서 나는 다음을 발견했습니다. 마이크 바니어의 기사 (Nicholas Mancuso에게 감사드립니다) 정말 도움이 되었습니다.나는 내 이해를 문서화하는 것 외에도 요약을 쓰고 싶습니다. 그것이 다른 사람들에게 도움이 될 수 있다면 매우 기쁠 것입니다.

에서 지겨운 에게 덜 엉터리

팩토리얼을 예로 들어 다음을 사용합니다. almost-factorial 숫자의 계승을 계산하는 함수 x:

def almost-factorial f x = if iszero x
                           then 1
                           else * x (f (- x 1))

위의 의사 코드에서, almost-factorial 기능을 발휘하다 f 그리고 숫자 x (almost-factorial 카레로 되어 있어서 기능을 가지고 있다고 볼 수 있어요 f 1항 함수를 반환합니다.)

언제 almost-factorial 에 대한 계승을 계산합니다. x, 이는 계승 계산을 위임합니다. x - 1 기능하다 f 그 결과를 다음과 같이 축적합니다. x (이 경우 (x - 1)의 결과를 x와 곱합니다).

다음과 같이 볼 수 있습니다. almost-factorial 을 받아들인다 지겨운 계승 함수 버전(숫자까지만 계산할 수 있음) x - 1) 그리고 다음을 반환합니다. 덜 형편없는 계승 버전(숫자까지 계산) x).다음과 같은 형식으로:

almost-factorial crappy-f = less-crappy-f

반복해서 통과하면 덜 형편없는 계승 버전 almost-factorial, 우리는 결국 원하는 계승 함수를 얻게 될 것입니다 f.다음과 같이 간주될 수 있습니다.

almost-factorial f = f

고정점

사실 그 almost-factorial f = f 수단 f 은 고정점 기능의 almost-factorial.

이것은 위의 함수들의 관계를 보는 정말 흥미로운 방법이었고 나에게는 아하 순간이었습니다.(아직 읽지 않았다면 Fix-Point에 대한 Mike의 게시물을 읽어 보십시오)

세 가지 기능

일반화하자면, 비재귀적 기능 fn (우리의 거의 계승과 마찬가지로) 우리는 고정점 기능 fr (저희 f처럼) 그럼 어쩌죠? Y 당신이 줄 때입니다 Y fn, Y 다음의 고정점 함수를 반환합니다. fn.

요약하면 (가정하여 단순화 fr 하나의 매개변수만 사용합니다. x 로 퇴화하다 x - 1, x - 2...재귀에서):

• 우리는 핵심 계산 ~처럼 fn: def fn fr x = ...accumulate x with result from (fr (- x 1)), 이것이 거의 유용하다 기능 - 사용할 수는 없지만 fn 직접적으로 x, 곧 유용할 것입니다.이 비재귀적 fn 기능을 사용합니다 fr 그 결과를 계산하기 위해
• fn fr = fr, fr 고정점이다 fn, fr 은 유용한 기능, 우리는 사용할 수 있습니다 fr ~에 x 결과를 얻으려면
• Y fn = fr, Y 함수의 고정점을 반환합니다. Y 우리의 거의 유용하다 기능 fn ~ 안으로 유용한 fr

파생 Y (포함되지)

파생은 생략하겠습니다 Y 그리고 이해하러 가세요 Y.Mike Vainer의 게시물에는 많은 세부 정보가 있습니다.

형태 Y

Y 는 다음과 같이 정의됩니다(에서 람다 미적분학 체재):

Y f = λs.(f (s s)) λs.(f (s s))

변수를 교체하면 s 함수의 왼쪽에서 우리는

Y f = λs.(f (s s)) λs.(f (s s))
=> f (λs.(f (s s)) λs.(f (s s)))
=> f (Y f)

그래서 실제로 그 결과는 (Y f) 고정점이다 f.

왜? (Y f) 일하다?

서명에 따라 f, (Y f) 단순화하기 위해 임의의 소수점의 함수일 수 있습니다. (Y f) 우리의 팩토리얼 함수처럼 하나의 매개변수만 취합니다.

def fn fr x = accumulate x (fr (- x 1))

~부터 fn fr = fr, 우리는 계속

=> accumulate x (fn fr (- x 1))
=> accumulate x (accumulate (- x 1) (fr (- x 2)))
=> accumulate x (accumulate (- x 1) (accumulate (- x 2) ... (fn fr 1)))

재귀 계산은 가장 안쪽에 있을 때 종료됩니다. (fn fr 1) 기본 사례이고 fn 사용하지 않는다 fr 계산에서.

보고 Y 다시:

fr = Y fn = λs.(fn (s s)) λs.(fn (s s))
=> fn (λs.(fn (s s)) λs.(fn (s s)))

그래서

fr x = Y fn x = fn (λs.(fn (s s)) λs.(fn (s s))) x

나에게 있어 이 설정의 마법 같은 부분은 다음과 같습니다.

• fn 그리고 fr 서로 의존하다: fr '랩' fn 안에서는 매번 fr 계산하는 데 사용됩니다 x, 그것은 '생성'('리프트'?) fn 그리고 그 사람에게 계산을 위임합니다. fn (그 자체로 전달 fr 그리고 x);반면에, fn 에 달려있다 fr 그리고 사용 fr 더 작은 문제의 결과를 계산하기 위해 x-1.
• 당시 fr 정의하는 데 사용됩니다. fn (언제 fn 용도 fr 운영 중), 실제 fr 아직 정의되지 않았습니다.
• 그것은 fn 실제 비즈니스 로직을 정의합니다.기반 fn, Y 창조하다 fr - 특정 형식의 도우미 함수 - 계산을 용이하게 하기 위해 fn 안에 재귀적 방법.

이해하는데 도움이 됐어요 Y 지금은 이 방법이 도움이 되기를 바랍니다.

그런데, 책도 찾았어요 람다 미적분학을 통한 함수형 프로그래밍 소개 아주 좋아요, 아직 일부만 진행 중이고 머리를 돌릴 수 없다는 사실도 있어요 Y 그 책이 나를 이 포스트로 이끌었다.

Answer 15

다음은 다음에 대한 답변입니다. 원래 질문, 다음에서 컴파일됨 기사 (완전히 읽을 가치가 있는 내용입니다) Nicholas Mancuso의 답변, 기타 답변:

Y-콤비네이터란 무엇입니까?

Y-combinator는 재귀적이지 않은 함수인 단일 인수를 취하고 다음과 같은 함수 버전을 반환하는 "기능적"(또는 다른 함수에서 작동하는 고차 함수)입니다. 재귀적.

---

다소 재귀적이지만 더 심층적인 정의는 다음과 같습니다.

결합자는 자유 변수가 없는 람다 표현식일 뿐입니다.
자유 변수 — 바인딩된 변수가 아닌 변수입니다.
바인딩된 변수 — 해당 변수 이름을 인수 중 하나로 갖는 람다 식의 본문 내부에 포함된 변수입니다.

이에 대해 생각하는 또 다른 방법은 콤비네이터가 람다 표현식이라는 것입니다. 여기서 콤비네이터의 이름을 발견된 모든 곳에서 해당 정의로 바꿀 수 있고 모든 것이 계속 작동하도록 할 수 있습니다(콤비네이터가 그렇게 하면 무한 루프에 빠지게 됩니다). 람다 본문 내부에 자신에 대한 참조가 포함되어 있습니다).

Y-조합기는 고정 소수점 조합기입니다.

함수의 고정점은 함수에 의해 자체적으로 매핑되는 함수 도메인의 요소입니다.
즉 말하자면, c 함수의 고정점이다 f(x) 만약에 f(c) = c
이는 다음을 의미합니다. f(f(...f(c)...)) = fn(c) = c

결합자는 어떻게 작동하나요?

아래 예에서는 다음과 같이 가정합니다. 강력 + 역동적 타자:

게으른(정상 순서) Y 조합자:
이 정의는 게으른 언어(또한:지연, 필요에 따라 호출) 평가 - 값이 필요할 때까지 표현식 평가를 지연시키는 평가 전략입니다.

Y = λf.(λx.f(x x)) (λx.f(x x)) = λf.(λx.(x x)) (λx.f(x x))

이것이 의미하는 바는 주어진 기능에 대해 f (비재귀 함수임) 해당 재귀 함수는 다음을 계산하여 먼저 얻을 수 있습니다. λx.f(x x), 그리고 이 람다 표현식을 자신에게 적용합니다.

엄격한(적용 순서) Y-조합자:
이 정의는 엄격한 언어(또한:열정적, 탐욕적) 평가 — 표현식이 변수에 바인딩되자마자 평가되는 평가 전략입니다.

Y = λf.(λx.f(λy.((x x) y))) (λx.f(λy.((x x) y))) = λf.(λx.(x x)) (λx.f(λy.((x x) y)))

본질적으로 게으른 것과 동일하며 단지 추가 기능이 있을 뿐입니다. λ 람다의 본문 평가를 지연시키는 래퍼.내가 물어봤어 다른 질문, 이 주제와 다소 관련이 있습니다.

그것들은 무엇에 좋은가요?

훔친 에서 빌린 Chris Ammerman의 답변:Y-combinator는 재귀를 일반화하고 구현을 추상화하여 해당 함수의 실제 작업과 분리합니다.

Y-combinator에는 몇 가지 실용적인 응용 프로그램이 있지만 이는 주로 이론적 개념에 불과하며 이를 이해하면 전반적인 비전이 확장되고 분석 및 개발자 기술이 향상될 가능성이 높습니다.

절차적 언어에 유용합니까?

처럼 Mike Vanier가 밝혔습니다.: 많은 정적으로 유형이 지정된 언어에서 Y 결합자를 정의하는 것이 가능하지만 (적어도 내가 본 예에서는) 이러한 정의에는 일반적으로 Y 결합자 자체에 간단한 정적 유형이 없기 때문에 명확하지 않은 유형의 해커가 필요합니다. .이 내용은 이 글의 범위를 벗어나므로 더 이상 언급하지 않겠습니다.

그리고 Chris Ammerman이 언급한:대부분의 절차적 언어에는 정적 유형이 있습니다.

그러니 이것에 답해 보세요. 실제로는 그렇지 않습니다.

Answer 16

고정 소수점 조합자(또는 고정 소수점 연산자)는 다른 함수의 고정 소수점을 계산하는 고차 함수입니다.이 작업은 언어 런타임 엔진의 명시적인 지원 없이 다시 쓰기 규칙의 형태로 재귀를 구현할 수 있으므로 프로그래밍 언어 이론과 관련이 있습니다.(소스 위키피디아)

Answer 17

this 연산자를 사용하면 생활이 단순화됩니다.

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

그런 다음 추가 기능을 피하십시오.

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

마지막으로, 당신은 전화 fac(5).

Answer 18

이에 답하는 가장 좋은 방법은 JavaScript와 같은 언어를 선택하는 것입니다.

function factorial(num)
{
    // If the number is less than 0, reject it.
    if (num < 0) {
        return -1;
    }
    // If the number is 0, its factorial is 1.
    else if (num == 0) {
        return 1;
    }
    // Otherwise, call this recursive procedure again.
    else {
        return (num * factorial(num - 1));
    }
}

이제 함수 내부에서 함수 이름을 사용하지 않고 계속해서 재귀적으로 호출하도록 다시 작성해 보겠습니다.

함수 이름이 있는 유일한 장소 factorial 통화 사이트에서 확인해야 합니다.

힌트:함수 이름은 사용할 수 없지만 매개변수 이름은 사용할 수 있습니다.

문제를 해결하세요.찾아보지 마세요.일단 해결하면 y-combinator가 어떤 문제를 해결하는지 이해하게 될 것입니다.