[Haskell-cafe] Uses of `fix' combinator
Derek Elkins
derek.a.elkins at gmail.com
Thu Feb 19 09:09:13 EST 2009
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))
More information about the Haskell-Cafe
mailing list