[Haskell-cafe] Re: Cute code [was: The C Equiv of != in Haskell miscommunication thread]

[Jon Fairbairn]

Vincent Kraeutler <vincent at kraeutler.net> writes:
> anyhow. if someone has a "pedestrian's guide to the fixed point
> operator" lying around, a link would be much appreciated.

At the risk of increasing rather than decreasing your
confusion (but in the hope that once you get over it you
will be enlightened), here's another approach to the
subject:

Suppose we have a language (either untyped or cleverly typed
-- the following won't typecheck in Haskell, but there are
ways around it) that allows non-recursive definitions
only. We want to define factorial, but it needs to call
itself.  How about we try to define a function that /when
applied to itself/ is factorial?

 half_fact me n = 
    if n <= 1
    then 1
    else n * ????? (n-1)
               ^
               |
what goes here? Well, we know that we are trying to arrange
that

 half_fact half_fact == factorial

so when we use it, the "me" parameter is going to be
half_fact, which implies that (me me) will be (half_fact
half_fact), which is factorial.  So we write:

 half_fact me n = 
    if n <= 1
    then 1
    else n * me me (n-1)

 factorial = half_fact half_fact

Now, in such a language we might write all our recursive
functions that way, or we might prefer not to have to double
up the names to get recursion, and abstract away the
operator that ties the knot: define a function that, given
the factorial function makes a step of the evaluation and
then lets factorial do the rest:

 step_towards_factorial factorial n =
    if n <=1 
    then 1
    else n * factorial (n-1)

put

 stf = step_towards_factorial

and observe that
 
stf (error "too deep") 1 == 1
stf (stf (error "too deep")) 2 == 2
stf (stf (stf (error "too deep"))) 3 == 6

"fix" just does that as many times as necessary, so we can
define

 factorial = fix step_towards_factorial

The connection between the "half function" approach and the
fix operator is this: we want fix f = (f (fix f)), which is
a recursive definition, so we can use the "half function"
technique to make it:

 half_fix me f = f (me me f)
 fix = half_fix half_fix



-- 
Jón Fairbairn                                 Jon.Fairbairn at cl.cam.ac.uk