Skip to content
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
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
Something went wrong with that request. Please try again.