StandardML中的y组合器 [英] y-combinator in StandardML

问题描述

我知道我可以像这样用SML编写y-combinator: 首先声明一个新的数据类型，以绕过由于圆度而导致的类型不匹配.

I know I can write the y-combinator in SML like this: First declare a new datatype to bypass the type mismatch due to circularity.

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

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

Now you can easily define the 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)))

然后，您就可以使用它了:

Then you are done, you can use it like this:

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

---

我的问题是:还有其他方法可以在SML中实现y-combinator吗?

---

My question is: Are there other ways of implementing the y-combinator in SML?

推荐答案

您当然可以使用内置的递归本身，例如

You can of course use the built-in recursion itself, e.g.

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

或

fun Y f x = f (Y f) x

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

You can also use exceptions in the same way as a datatype, but only 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))

但我相信，有关它的参考文献也涵盖了它.

But I believe along with references that about covers it.

实际上，您可以使用 local 异常将其变为多态:

Actually, you can make it polymorphic by using a local exception:

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组合器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！