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