Ex 9.9 in Paul Hudak's book

[Paul Hudak]

> What I would like to know is how the 'fix' function could be used
> to find the fixed point of a function like ( \n -> 2*n ).

Olaf and Lennart said a little about least fixpoints, but little about
what makes a fixpoint least.  Olaf suggested looking up papers on domain
theory or denotational semantics to understand it better.  But the idea
is really simple: just think of it as an ordering on information
content.  Bottom (_|_) contains NO information, and is thus the least
value in any domain.  The integers 1, 2, 3, etc. contain the same
"amount" of information, but the information in each case is different
-- thus these values are incomparable in the information ordering.  So
even though \n -> n has all these values as fixpoints, the LEAST one is
_|_.  As for \n -> 2n, even though 0 is a fixpoint, the LEAST one is
_|_.  And fix will find these for you, in the sense that fix applied to
each of these functions leads to non-termination, and non-termination is
equivalent to bottom, since it yields NO information.  (The fact that in
some implementations the stack or heap will blow up is an implementation
artifact.)

> If it isn't possible, can someone explain the crucial difference
> between n! and (\n -> 2*n) which allows n factorial to be found via
> the fix point method and not zero.

fix is able to find the fixpoint of:
  \f -> \n -> if (n==0) then 1 else n*f(n-1)
This fixpoint is a FUNCTION, not the factorial value itself.  So they
are very different.

Which begs the question: can fix find fixpints that are not functions,
and not bottom?  Consider this well-known example:

  ones = 1 : ones

We can write this as:

  ones = (\wons -> 1 : wons) ones

and thus:

  ones = fix (\wons -> 1 : wons)

Try this in Hugs, and see what happens when you type "take 10 ones" at
the prompt.

  -Paul