2016-11-19 10 views
6

나는 SML에서 다음과 같이 y 결합자를 쓸 수 있음을 알고 있습니다. 원형으로 인해 유형 불일치를 피하기 위해 먼저 새로운 데이터 유형을 선언하십시오.StandardML의 y 결합 자

val Y = fn f => (fn x => fn a => f (unroll x x) a) 
      (Roll (fn x => fn a => f (unroll x x) a))) 

그런 다음 작업을 완료, 당신은 다음과 같이 사용할 수 있습니다 :

val f = Y (fn f => fn n => if n = 0 then 1 else n * f (n-1)) 

내 질문은

datatype 'a mu = Roll of ('a mu -> 'a) 
val unroll = fn Roll x => x 

지금 당신은 쉽게, Y 콤비를 정의 할 수 있습니다 : SML에서 y-combinator를 구현하는 다른 방법이 있습니까?

답변

5

물론 내장 된 재귀 자체를 사용할 수도 있습니다.

fun Y f = f (fn x => Y f x) 

또는

fun Y f x = f (Y f) x 

또한 데이터 타입과 같은 방식으로 예외를 사용할 수 있지만 monomorphically : 나는 약을 다루고 있음을 언급과 함께 생각

exception Roll of exn -> int -> int 
val unroll = fn Roll x => x 
fun Y f = (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a)) 

하지만.

편집 : 사실, 당신은 지역 예외를 사용하여 다형성 할 수 있습니다 :

fun Y f : 'a -> 'b = 
    let 
    exception Roll of exn -> 'a -> 'b 
    val unroll = fn Roll x => x 
    in 
    (fn x => fn a => f (unroll x x) a) (Roll (fn x => fn a => f (unroll x x) a)) 
    end 
+0

당신은 할 수없는, 즉 필요한 자체 응용 프로그램은 재귀 유형이 필요하기 때문이다. –

+0

@ NaCl 음, "fun"는 'val rec'의 파생 형식이므로 'fun'를 사용하는 것과 동일 할 수 있습니다. – matt