[MLton] Fixed points in SML

[Wesley W. Terpstra]

On Aug 30, 2006, at 12:34 PM, Vesa Karvonen wrote:
> val Y =
>     fn f =>
>        let
>           val f' = ref (fn _ => raise Fail "Y")
>           val f'' = fn x => !f' x
>        in
>           f' := f f''
>         ; f''
>        end
Nice. I had completely forgotten about using side effects.

>           exception E of exn -> 'a -> 'b
That, however, would be a datatype. :-)

>> let rec fix f x = f (fix f) x
> I assume Wesley wants to disallow the use of built-in recursion as  
> well.
I did, but skaller's implementation is definitely the prettiest. :-)

> A function of type
>    ('a -> 'a) -> 'a
> can not return normally in SML.  Intuitively the reason for this is
> that the function would need to create a value of any type and that
> is impossible

Makes sense to me. However, I think the problem has more to do with  
laziness. I bet if you did it in Haskell, it would work.
   val Y : ('a -> 'a) -> 'a = fn g => (fn x => x (T x)) (fn (T x) =>  
g (x (T x)))
The (x (T x)) need not be evaluated right away in Haskell, so only if  
the recursive call is needed would a lazy language need to evaluate  
the parameter.

I am no Haskell programmer, but
   val Y : ((unit -> 'a) -> 'a) -> 'a = fn g => (fn x => x (T x)) (fn  
(T x) => fn () => g (x (T x))) ()
seems to do much the same thing that a lazy language would.