Y combinator

[Andrew Butterfield]

>Does somebody know how to derive the Y combinator in Clean?
>I tryed to write a Y combinator in Clean, by failed. Of course, it is
>easy to write something like this:
>
>Y  f= f (Y f)
>
>However, I would like to have something like this:
>
>Y f= ((\f x-> f x x) ((\ f g x->(f (g x))) f))
>              ((\f x-> f x x) ((\ f g x->(f (g x))) f))

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


The combinator  Y` defined as   Y` f = f (Y` f)  is writable,
and has type  (A -> A) -> A
but basically relies on the inbuilt recursion support to work.

If all you want is a combinator that acts like the Y combinator,
then use Y`

-------------------------------------------------------------
Andrew Butterfield,                           Location: LG.19
Dept. of Computer Science,               Tel: +353-1-608-2517
O'Reilly Institute,                      Fax: +353-1-677-2204
Trinity College,
Dublin 2, IRELAND.        mailto:Andrew.Butterfield@cs.tcd.ie
URL:                 http://www.cs.tcd.ie/Andrew.Butterfield/