Instantly share code, notes, and snippets.

# WillNess/fix-question.hs Last active Jul 4, 2016

What would you like to do?
 -- 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!