Y-combinator in StandardML

Question

I know that I can write y-combinator in SML as follows: First declare a new data type to circumvent type mismatch due to roundness.

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

Now you can easily define y-combinator:

 val Y = fn f => (fn x => fn a => f (unroll xx) a) (Roll (fn x => fn a => f (unroll xx) a))) 

Then you are done, you can use it as follows:

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

---

My question is: are there other ways to implement y-combinator in SML?

Answer 1

Of course you can use inline recursion like

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

or

 fun Y fx = f (Y f) x 

You can also use exceptions in the same way as a data type, but only monomorphically:

 exception Roll of exn -> int -> int val unroll = fn Roll x => x fun Y f = (fn x => fn a => f (unroll xx) a) (Roll (fn x => fn a => f (unroll xx) a)) 

But I believe along with links to covers.

Edit: In fact, you can make this polymorphic 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 xx) a) (Roll (fn x => fn a => f (unroll xx) a)) end