기능 프로그래밍을위한 람다 미적분학

Question

Lambda 미적분학 (λ x. λ y. λ s. λ z. xs (YSZ))에서 두 개의 교회 숫자를 추가하는 데 사용됩니다. 우리는 이것을 어떻게 설명 할 수 있습니까? 당신의 도움은 대단히 감사합니다

Answer 1

실제로 λ f1. λ F2. λ s. λ z. (F1 S (F2 SZ))는 F2로 표시되는 숫자 인 (F2 SZ), 내부 (F1 SZ)로 대체 (F2 SZ)를 대체하기 때문에 추가를 계산합니다.

예 : F2에 대해 2 개를 가져 가겠습니다. s s z 확장 된 형태로. F1은 하나입니다. s z. 마지막으로 교체하십시오 z f2에 의해 당신은 얻습니다 s s s z, 세 가지에 대한 확장 된 형태.

칠판과 손을 흔들면 더 쉬울 것입니다. 죄송합니다.

Answer 2

Lambda 미적분학에서는 유도 된 작업 측면에서 데이터 유형을 코딩합니다. 예를 들어, 부울은 입력 두 값 a와 b를 취하는 선택 함수이며 a 또는 b를 반환합니다.

                      true = \a,b.a   false = \a,b.b

자연 수의 사용은 무엇입니까? 주요 계산 목적은 반복에 결속을 제공하는 것입니다. 따라서 기능 F, 값 x를 입력하는 연산자로서 자연 숫자를 코딩하고 n 번 x 이상의 적용을 반복합니다.

                        n = \f,x.f(f(....(f x)...))

f의 n 발생.

이제 X에서 시작하는 함수 F를 N + M 회 반복하려면 N 번 반복을 시작해야합니다.

                                m f (n f x)

마찬가지로, N*m Times를 반복하려면 M 회 반복 N 회 반복 N Times F (두 개의 중첩 루프에서와 같이)의 작동이 필요합니다.

                                 m (n f) x  

데이터 타입의 이전 인코딩은 생성자 및 해당 제거기 (소위 BOHM-Berarducci 인코딩) 측면에서보다 공식적으로 설명됩니다.