[Haskell-beginners] Y-combinator

[Jon Harrop]

On Thursday 25 February 2010 00:31:59 Brent Yorgey wrote:
> On Wed, Feb 24, 2010 at 11:53:50PM +0000, Jon Harrop wrote:
> > On Wednesday 24 February 2010 20:53:14 Edward Z. Yang wrote:
> > > http://haskell.org/hoogle/3/?q=fix
> >
> > That leads to the following source:
> >
> > http://haskell.org/ghc/docs/latest/html/libraries/base/src/Data-Function.
> >html
> >
> > but it uses a workaround rather than extending the type system. I'm
> > looking for an equivalent of OCaml's -rectypes that enables recursive
> > types in Haskell (e.g. in ghci)?
>
> Haskell has recursive types, but they are iso-recursive rather than
> equi-recursive; the recursion must always be guarded by a data
> constructor.  I am not sure what you mean by saying that Data.Function
> contains a "workaround".

Guarding the recursion with a constructor is the workaround I was referring 
to, like this:

# let fix f =
    (fun (`X x) -> f(x (`X x))) (`X(fun (`X x) y -> f(x (`X x)) y));;
val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

> What exactly are you trying to do? 

I'm wondering if it is possible to get this to type in Haskell without 
altering the code, i.e. by enabling recursive types in the compiler as I did 
with OCaml using -rectypes.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e