Create a gist now

Instantly share code, notes, and snippets.

-- 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!
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment