By the way, the fact that "least" is in the sense of "least defined" explains why fix (2^) gives an undefined: The least defined fixpoint of any strict function (f : f _|_ = _|_) is, by definition, undefined. And (2^) is strict.
2009/2/19 Derek Elkins <derek.a.elk...@gmail.com>: > 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 > -- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe