OCaml의 익명 재귀 함수

Question

어떻게 익명의 재귀 함수를 만드나요 (factorial n과 같은 간단한 것입니까?) 가능하다고 들었지만 OCaml에서 어떻게 작동시키는 지 모르겠습니다.

let a = 
    fun x -> .... 

다음

Answer 1

는 익명 함수를 사용하여 계승의 정의는 내가 그냥 계속하는 방법을 모른다

... :

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

그것은 -rectypes의 사용을 필요로 깃발.

$ rlwrap ocaml -rectypes 
     OCaml version 4.03.0 

let fact = 
    (fun f -> (fun x a -> f (x x) a) (fun x a -> f (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1));; 
val fact : int -> int = <fun> 
# fact 8;; 
- : int = 40320 

내가 여기에 Y 연결자를보고 다소 사기 :

여기에 작동하는지 보여주는 세션의 Rosetta Code: Y Combinator

업데이트를

면책 조항 : 당신은 읽을 잘 할 것 고정 소수점 및 Y Combinator에 대한 정보를 얻는 것보다 나에게 정보를 제공하는 것입니다. 나는 이론가가 아니라 겸손한 수련생입니다.

실제 계산은 거의 불가능합니다 (그러나 확실히할만한 가치가 있습니다). 그러나 높은 수준에서 아이디어는 이와 같습니다.

정의의 첫 번째 줄은 일반적으로 함수의 고정 점을 계산하는 Y 결합 자입니다. 재귀 함수는 함수에서 함수로의 고정 된 점입니다.

첫 번째 목표는 고정 소수점이 계승 함수 인 함수를 찾는 것입니다. 그것이 정의의 두 번째 줄입니다. 유형을 int -> int으로 지정하면 int -> int 유형의 다른 기능을 다시 제공합니다. 계승 함수를 주면 계승 함수를 돌려줍니다. 이것은 계승 함수가 고정 점이라는 것을 의미합니다.

그래서이 함수에 Y 결합자를 적용하면 실제로 계승 함수를 얻습니다.

Answer 2

Jeffrey Scofield의 대답에 대해 좀 더 자세히 설명하겠습니다. 익명 재귀 함수는 실제 재귀 호출 (우리의 경우 fact (n - 1))을 수행하는 방법입니다 정의 할 때 계승 기능의 익명이 아닌 재귀 적 정의는

let rec fact n = 
    if n < 2 then 1 else n * fact (n - 1) 

발생할 첫 번째 문제가 될 수 있습니다. 호출에는 이름이 필요하며 익명 함수의 이름은 없습니다. 해결책은 임시 이름을 사용하는 것입니다. 임시 이름 f으로 정의 기관은 "임시 이름"f 언 바운드 때문에 단지

fun n -> if n < 2 then 1 else n * f (n - 1) 

이 용어는 유형이없는 것입니다. 그러나 우리는 f의 경계를 지정하여 유형을 갖는 값으로 변환 할 수 있습니다. 우리가 결과를 g을 부르 자 :

let g = fun f n -> if n < 2 then 1 else n * f (n - 1) 

g 아직 순간에 익명이 아니라 오직 내가 다시 참조 할 때문이다. g은 (int -> int) -> (int -> int)입니다. 우리가 원하는 (계승 함수) 유형은 (int -> int)입니다. 따라서 g은 우리가 원하는 유형 (이 경우 함수 유형)을 취하고 같은 유형의 것을 만듭니다. 직관은 g이 계승 함수의 근사값을 취한다는 것인데, 모든 n에 대해 최대 N까지 작동하고 더 가까운 근사값을 반환하는 함수, 즉 f이 있습니다. 즉, N 모두 +1 n까지 작동하는 함수입니다.

마지막으로 g을 실제 재귀 적 정의로 바꾸는 것이 필요합니다. 이렇게하는 것은 매우 일반적인 작업입니다. g은 근사 품질을 향상시킵니다. 최종 계승 함수 fact은 더 이상 개선 할 수없는 계급 함수입니다. 따라서 g을 fact에 적용하는 것은 단지 fact과 같아야합니다. (실제로는 가치의 관점에서만 볼 수 있습니다. 일부 n의 경우 g fact n에 고유 한 실제 계산은 단지 fact n의 것과 다르지만 반환 값은 같습니다.) 즉, fact은 고정 소수점 g입니다. . 그래서 우리가 필요로하는 것은 고정 점을 계산하는 것입니다.

운 좋게도 다음과 같은 기능이 있습니다. Y 결합 자. 값의 관점에서 볼 때, Y combinator (OCaml에서 대문자는 생성자 용으로 예약되었으므로 y을 사용하자)는 g에 대해 y g = g (y g) : 일부 함수 g이 주어지면 연결자는 고정 소수점 중 하나를 반환합니다. 우리의 경우 따라서

y : (`a -> `a) -> `a 

는 입력 변수 (int -> int) 인스턴스화된다. y를 정의하는 한 가지 방법은

let y = fun g -> (fun x -> g (x x)) (fun x -> g (x x)) 

것이다 그러나 이것은 (내가 믿는로, 하스켈이있다)에만 게으른 평가와 함께 작동합니다. OCaml은 열심히 평가하므로, 사용될 때 스택 오버플로를 생성합니다. 그 이유는 OCaml의 적 g 전화를받지 않고

g (y g) 8 
g (g (y g)) 8 
g (g (g (y g))) 8 
... 

에 y g 8 같은 것을 설정하는 시도이다. 용액 y 내부 지연 계산을 사용하는 것이다

let y = fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a) 

단점이 y 어떤 임의의 2 종류 이상 작동하지 않는다는 것이다. 함수 유형에서만 작동합니다.

y : ((`b -> `c) -> (`b -> `c)) -> (`b -> `c) 

하지만 다른 값에 대한 재귀 정의가 아니라 어쨌든 함수의 재귀 정의를 요청했습니다. 따라서 계승 함수의 정의는 y g이고 y 및 g은 위와 같습니다. 나도 y도 g 아직 익명없는,하지만 쉽게 해결 될 수 있습니다

(fun g -> (fun x a -> g (x x) a) (fun x a -> g (x x) a)) 
    (fun f n -> if n < 2 then 1 else n * f (n - 1)) 

UPDATE :

y를 정의하는 것은 단지 -rectypes 옵션을 사용할 수 있습니다. 그 이유는 x을 자체에 적용하기 때문입니다.