y-combinator in StandardML

Question

我知道我可以這樣寫SML中的y-combinator，如下所示： 首先聲明一個新的數據類型來繞過由於圓形造成的類型不匹配。

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

現在您可以輕鬆定義的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)) 

---

我的問題是：在SML中還有其他實現y-combinator的方法嗎？

Answer 1

你當然可以使用內置的遞歸本身，例如，

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