The Haskell Fixpoint Combinator
Yesterday, I had reason to consider the problem of finding a function's fixed point: the value at which it evaluates to that value (i.e. \(x|f(x)=x\). Haskell defines a function for finding this for an arbitrary function: fix:
fix :: (a -> a) -> a fix f = let x = f x in x
Naturally, I spent the rest of the afternoon figuring this out.
Rebecca Skinner explains that what we have here is a "recursive let binding": a let binding in which a bound name appears on the right-hand side of the same (or another, if we're introducing more than one binding) binding, which induces recursion.
Let's work-out a few examples. What happens if we try to find a fixed point for the function (2+) (i.e. the function that adds two to its argument)? Well:
fix (2+) = let x = (2 + x) in x
We begin recursively rewriting \(x\) on the right-hand side (in "let blah = blah in expr", the thing being evaluated is "expr"), to get:
fix (2+) = let x = (2 + x) in x = let x = (2 + x) in (2 + x) = let x = (2 + x) in (2 + (2 + x)) = let x = (2 + x) in (2 + (2 + (2 + x))) = let x = (2 + x) in (2 + (2 + (2 + (2 + x)))) = ...
Haskell is in general lazy in its evaluation, but the function (2+) is strict in its argument; it needs to evaluate it to continue. So this function will never finish.
That said, it gives us some intuition. For \(fix f\) to terminate, \(f\) must either not force its argument, or somehow "reduce" it in such a way as to eventually terminate the recursion. Let's look at the first case with the function const. Simply writing-out the definition of fix gives us:
fix (const 11) = let x = const 11 x in x
Next, we rewrite the right-hand \(x\) in terms of the let binding:
= let x = const 11 x in const 11 x
----------
Since const ignores its second argument, the expression immediately evaluates to just 11. The constant 11 is independent of the let binding (i.e. \(x\) doesn't appear anywhere in our expression now), so we're done:
= let x = const 11 x in 11 = 11
For the second possible way to get \(fix\) to terminate, let's consider the example given in the hackage documentation linked above: computing the factorial function via fix:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3
Let's just clarify this a bit: the argument to \(fix\) is a lambda taking two arguments, the first of which is a function Int -> Int, and the second of which is an Int. Un-Currying, we see that the argument type can be expressed as (Int -> Int) -> (Int -> Int): give me a function (rec) from Int to Int, and I'll return a function from \(n\) (an Int) to Int.
Now, recall the type of \(fix\):
fix :: (a -> a) -> a
The type variable \(a\) in our case resolves to Int -> Int, so this type checks: the lambda we're handing to fix is of type (Int -> Int) -> (Int -> Int), so
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1))
is of type Int -> Int. Applying that to 3 will yield another Int.
How does it evaluate? Again just writing-out the defintion of \(fix\) gives:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = (let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x) 3
We can move the 3 into the let binding:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3
and evaluate the let binding to get:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 3
Simply performing the substitution gives us:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * (x 2)
Now, let's rewrite the right-most \(x\) in terms of the let binding:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * (x 2) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * ((\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 2)
and just perform the subsitution again:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * (x 2) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * ((\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 2) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * 2 * (x 1)
Another recursive evaluation of the let binding and function application finally yields:
fix (\rec n -> if n <=1 then 1 else n * rec (n - 1)) 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 3 = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * (x 2) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * ((\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 2) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * 2 * (x 1) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * 2 * ((\rec n -> if n <=1 then 1 else n * rec (n - 1)) x 1) = let x = (\rec n -> if n <=1 then 1 else n * rec (n - 1)) x in 3 * 2 * 1 = 6
We that that \(fix\) terminated because we invoked it on a function that "reduced" its argument in some way and provided a "base case", meaning that the recursion eventually terminated.
12/02/25 20:17