y-combinator in StandardML

Question

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

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

---

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

Cavalryman

Answer 1

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

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

or

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.

Edit: 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

Deckhouse

You can't, since the self application necessary for that requires a recursive type. – Deckhouse

@Cavalryman well, you kind of can, since "fun" is a derived form, of 'val rec' but it would be equivalent to using 'fun'. – Coit