Y 조합

1866 단어
Y 조합자가 해결하고자 하는 문제는 어떻게 순수한 lambda 표현식으로 귀속을 단계승으로 실현하는가이다. 아래의 코드로 귀속의 형식으로 표현할 수 있다.
f n = if n > 1 then n * f (n-1) else 1

자연수 n의 곱셈을 요구하려면 f n만 호출하면 상기 코드는 하나의 부수문장을 포함할 수 있다. 그러나 순수한 lambda표현식은 부수문장이 없다. 그러면 순수한 lambda표현식으로 귀속을 실현할 수 있을까?
곱셈을 구할 수 있는 함수는 여러 개가 있다고 추측할 수 있다. 예를 들어f n = foldl (*) [1..n]가 그 중의 하나이다.그래서 우리는 곱셈을 구할 수 있는 함수f를 변수로 삼아 곱셈을 정의하면 구f의 값이 된다.
정의
g f = 
 -> if n > 1 then n * f (n-1) else 1

먼저 결론을 내린다. f가 계승을 구할 수 있는 충분한 필요조건은 g f == f(==의 등효 표시, 아래와 같다)
다음은 엄격하지 않게 증명해 보겠습니다.
  • 의 필요성 가설f이 곱셈을 계산할 수 있다면 g을 f에 응용하면 새로운 함수g f, 즉
    -> if n > 1 then n * f (n-1) else 1    f를 얻을 수 있다. g f는 곱셈을 계산할 수 있고 곱셈의 정의에 의하면g f == f도 반드시 곱셈을 계산할 수 있다. 즉g f == f
  • 충분성 만약f ==
    -> if n > 1 then n * f (n-1) else 1    이라면 대환을 통해 얻을 수 있다g f == f. 이것이 바로 우리가 위에서 제시한 곱셈의 귀속 정의 형식이다. 이런 f가 곱셈을 계산할 수 있다는 것을 확정할 수 있고 수학 귀납법을 통해 증명할 수 있다
    • 종합하면 알 수 있듯이 g f == f는 f가 곱셈을 계산할 수 있는 충분한 필요조건이다
    그러면 문제는'방정식f == Y g의 해를 구하는 것'으로 바뀌었다.
    분명히 f는 g에 관한 함수일 것이다. 그러면 Y조합자는 사실 이 함수이다.f하지만 구체적으로 어떻게 이 해답을 구하기는 너무 어려워요. 민과인 저는 선배들이 남긴 결론을 이용해서 천천히 모을 수밖에 없어요.gen gen이런 형식으로gen만족해야 한다
    gen = \x -> g (x x)

    그리하여 gen gen = g gen gen이렇게 해서 g의 움직임을 찾았어요.
    지금부터 Y조합자 구성: 위에서 논의한 바와 같이 알 수 있다Y g == f == gen gen == g gen gen칙
    Y g = g gen gen

    즉
    Y g = gen gen

    즉
    Y g = (\x -> g (x x)) (\x -> g (x x))

    이로부터 Y 조합을 얻었다.
    백준 10000번: 원 영역
    안전한 웹 응용 프로그램 제작 환경에 막힌 지점 구축(Mac)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage