correction to answer http://stackoverflow.com/a/4787707/849891

fix-question.hs

-- correction to answer http://stackoverflow.com/a/4787707/849891
-- answered Jan 24 '11 at 22:00 by Thomas M. DuBuisson

You need a way for the fixpoint to terminate.  Expanding your example, it's obvious it won't finish:

    fix id
    --> let x = id x in x
    --> let x = x in x
    --> let x = x in x
    --> ...

Here is a real example of me using fix (note I don't use fix often and was probably tired / not worrying 
about readable code when I wrote this):

    (fix (\f h -> if (pred h) then f (mutate h) else h)) q               -- fix g = let { f = g f } in f
    
                              -- = (let { f = (\f h -> if (pred h) then f (mutate h) else h) f } in f) q
                              -- = let { f h = if (pred h) then f (mutate h) else h } in f q

WTF, you say!  Well, yes, but there are a few really useful points here.  Foremost, your 
first `fix` argument should be a function which is called to perform the recursion, and the   
second argument is the data on which to act.  Here is the same code using a named function:

    let f h | pred h = f (mutate h)
            | otherwise = h
    in  f q

If you're still confused then perhaps *factorial* will be an easier example:

    fix (\rec d -> if d > 0 then d * (rec (d-1)) else 1) 5 -->* 120

Notice the evaluation:

    fix (\rec d -> if d > 0 then d * (rec (d-1)) else 1) 3 -->
    (let x = (\rec d -> if d > 0 then d * (rec (d-1)) else 1) x in x) 3 -->
    let x  = (\rec d -> if d > 0 then d * (rec (d-1)) else 1) x in x 3 -->
    let x  = (\    d -> if d > 0 then d * (x   (d-1)) else 1)   in x 3 -->

Oh, did you just see that?  That `x` became a function inside our `then` branch. When the 
definition (`(\rec d -> ...) x`) for `x` in `x 3` is forced to WHNF, the result is calculated 
and remembered, to be used henceforth:

    let x = (\d -> ...) in if 3 > 0 then 3 * (x (3-1)) else 1 -->
    let x = (\d -> ...) in 3 * (x 2) -->
    let x = (\d -> ...) in 3 * ((\d -> if d > 0 then d * (x (d-1)) else 1) 2) -->

In the above the updated, WHNF-reduced value of `x` is used, the `(\d -> ...)` expression.

    let x = (\d -> ...) in 3 * (if 2 > 0 then 2 * (x (2-1)) else 1) -->

And I'll stop here!