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...@. > > 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)) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
