Y组合子在Standard ML中的应用

Question

我知道可以这样在SML中编写Y组合子：

首先，声明一个新的数据类型以绕过由于循环引用造成的类型不匹配问题。

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组合子的方法？

- NaCl

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

- Andreas Rossberg

---

无法这样做，因为自应用需要递归类型。 - Andreas Rossberg

@NaCl 嗯，你有点可以，因为“fun”是“val rec”的派生形式，但使用“fun”等效。 - matt