Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
-- 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
thunk `x` in `x 3` is forced to WHNF, the result is calculated and remembered, to be used
henceforth:
let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1 -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->
In the above the updated value of `x` is used, the `(\d -> ...)` expression.
let x = ... 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.