Y combinator in Haskell
dm-list-clas...@scs.stanford.edu
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