Vincent Kraeutler
anyhow. if someone has a "pedestrian's guide to the fixed point operator" lying around, a link would be much appreciated.
At the risk of increasing rather than decreasing your confusion (but in the hope that once you get over it you will be enlightened), here's another approach to the subject: Suppose we have a language (either untyped or cleverly typed -- the following won't typecheck in Haskell, but there are ways around it) that allows non-recursive definitions only. We want to define factorial, but it needs to call itself. How about we try to define a function that /when applied to itself/ is factorial? half_fact me n = if n <= 1 then 1 else n * ????? (n-1) ^ | what goes here? Well, we know that we are trying to arrange that half_fact half_fact == factorial so when we use it, the "me" parameter is going to be half_fact, which implies that (me me) will be (half_fact half_fact), which is factorial. So we write: half_fact me n = if n <= 1 then 1 else n * me me (n-1) factorial = half_fact half_fact Now, in such a language we might write all our recursive functions that way, or we might prefer not to have to double up the names to get recursion, and abstract away the operator that ties the knot: define a function that, given the factorial function makes a step of the evaluation and then lets factorial do the rest: step_towards_factorial factorial n = if n <=1 then 1 else n * factorial (n-1) put stf = step_towards_factorial and observe that stf (error "too deep") 1 == 1 stf (stf (error "too deep")) 2 == 2 stf (stf (stf (error "too deep"))) 3 == 6 "fix" just does that as many times as necessary, so we can define factorial = fix step_towards_factorial The connection between the "half function" approach and the fix operator is this: we want fix f = (f (fix f)), which is a recursive definition, so we can use the "half function" technique to make it: half_fix me f = f (me me f) fix = half_fix half_fix -- Jón Fairbairn Jon.Fairbairn@cl.cam.ac.uk