标准ML中的y-combinator

Question

我知道我可以像这样在SML中编写y-combinator:首先声明一个新的数据类型以绕过由于循环引起的类型不匹配.

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

现在您可以轻松定义y-combinator:

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

您也可以使用与数据类型相同的方式使用异常,但只能以单态方式使用异常:

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