StandardML 中的 y 组合器

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 组合器？

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))

但我相信连同参考文献都涵盖了它。

编辑：实际上，您可以使用 local 异常使其成为多态的：

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

StandardML 中的 y 组合器

y-combinator in StandardML

functional-programming

sml

y-combinator