Y combinator

In class, someone pointed out that the standard definition of fix I
gave was kind of unsatisfying:

    fix f = let x = f x in x

because it uses recursion.  So if the point is to implement recursion
without recursion, then since fix uses recursion, I didn't really
achieve the goal.  Really the point was to set up for mfix, but still
this was a valid point.

The next question raised was whether you could something like the Y
combinator in Haskell.  The Y combinator is a fixed point combinator
for the untyped lambda calculus, which can be described by the
following pseudo-Haskell code:

    y f = (\x -> f (x x)) (\x -> f (x x))

Now, why is this pseudo-Haskell?  The problem is that Haskell is more
like a *typed* lambda calculus.  And so somehow we would need to have
type for x, which is being applied to itself.  In fact, it is not
possible to apply a function to itself in Haskell, because there is no
valid type for x.

As it happens, in order to apply a function to itself in the typed
lambda calculus, you need recursive types.  There are basically two
kinds of recursive types.  True, transparently recursive types are
called equi-recursive types.  Haskell doesn't support equi-recursive
types, but if it did, you could define a recursive type alias as
follows:

    type SelfApply t = (SelfApply t) -> t

Then if the type of x were SelfApply t, the type of x x would be t,
and you could use this to build a Y combinator.  But we can't since
Haskell won't allow the above SelfApply.

What Haskell does support is so-called iso-recursive types.  These are
recursive types, but in which there is a constructor, so that to
expose the recursive instance of the type, you must unpack the
constructor.  Happily, iso-recursive types are good enough to
implement self-application and the Y combinator, it's just a bit more
cumbersome.

So here you go, the Y combinator in Haskell:

    newtype SelfApply t = SelfApply { selfApply :: SelfApply t -> t }

    y :: (t -> t) -> t
    y f = selfApply term term
        where term = (SelfApply $ \x -> f (selfApply x x))

David