fixed point
Paul Hudak
paul.hudak at yale.edu
Mon Oct 27 09:46:09 EST 2003
> Also, had a feeling the fix function was related to the "Y"
> combinator; it seems they're the same thing!
Yes, they're the same in effect, although historically fix is often
defined recursively or taken as a primitive, whereas Y has its roots in
the lambda calculus, where it is defined as:
Y = \f.(\x.f(x x))(\x.f(x x))
which, you will note, is not recursive, yet has the property that Y f =
f (Y f), so that it is in fact a fixpoint generator. (You might want to
try proving this -- it's easy and illuminating.)
Unfortunately, this expression will not type-check in Haskell or ML
because of limitations of the Hindley-Milner type system :-(. There are
ways around this, but they involve introducing a data structure to avoid
problems with infinite types.
-Paul
More information about the Haskell-Cafe
mailing list