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
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
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