[Haskell-cafe] Uses of `fix' combinator

[Derek Elkins]

On Thu, 2009-02-19 at 17:00 +0300, Khudyakov Alexey wrote:
> Hello,
> 
> While browsing documentation I've found following function 
> 
> > -- | @'fix' f@ is the least fixed point of the function @f@,
> > -- i.e. the least defined @x@ such that @f x = x at .
> > fix :: (a -> a) -> a
> > fix f = let x = f x in x
> 
> I have two questions. How could this function be used? I'm unable to imagine 
> any. Naive approach lead to nothing (no surprise):
> 
> Prelude Data.Function> fix (^^2)
> <interactive>: out of memory (requested 2097152 bytes)
> 
> 
> Second question what does word `least' mean?`a' isn't an Ord instance. 

Least defined, i.e. least in the definability order where undefined <=
anything (hence also being called bottom) and, say, Just undefined <=
Just 3 and 1 </= 2 and 2 </= 1.  Fix is the basic mechanism supporting
recursion (theoretically).

The idea is when you have a recursive definition, you can abstract out
the recursive uses and apply fix to the resulting function, e.g.

ones = 1:ones
ones = fix (\ones -> 1:ones)

fact 0 = 1
fact n | n > 1 = n * fact (n-1)
fact = fix (\fact n -> case n of 0 -> 1; _ | n > 1 -> n * fact (n - 1))