[Haskell-beginners] Y-combinator

[Nicolas Pouillard]

On Thu, 25 Feb 2010 03:32:25 +0000, Jon Harrop <jon at ffconsultancy.com> wrote:
> 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>

If the reason for avoiding a data constructor is performances, then Haskell
"newtype"s will help.

-- 
Nicolas Pouillard
http://nicolaspouillard.fr