Y combinator

Antonio Eduardo Costa Pereira costa@ufu.br
Mon, 6 Dec 1999 19:28:34 -0200


> You cannot write the Y combinator in any strongly-typed (Hindley-Milner-like)
> language - it has an infinite type in such typing schemes
> 
> Y : x -> x -> x -> x -> x -> ....

Dear Andrew.
I still have a question. If I cannot write the Y combinator in any 
strongly-typed (Hindley-Milner-like) language, how can I write 
it in ML? After all, ML is the first language to use Hindley-Milner 
algorithm. The code below works perfectly well in ML:

datatype 'a t = T of 'a t -> 'a

 val y = fn f => (fn (T x) => (f (fn a => x (T x) a)))
                   (T (fn (T x) => (f (fn a => x (T x) a))))

val fat y (fn again => (fn x => if x<1 then 1 
                                           else (x*(again (x-1))  )))

Isn't it possible to write similar code in Clean? Why not?

Eduardo Costa