fixed point

[Paul Hudak]

 > 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