[Haskell-cafe] Uses of `fix' combinator

[Eugene Kirpichov]

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



-- 
Eugene Kirpichov
Web IR developer, market.yandex.ru