How do I use fix, and how does it work?

Question

I was a bit confused by the documentation for fix (although I think I understand what it's supposed to do now), so I looked at the source code. That left me more confused:

fix :: (a -> a) -> a
fix f = let x = f x in x

How exactly does this return a fixed point?

I decided to try it out at the command line:

Prelude Data.Function> fix id
...

And it hangs there. Now to be fair, this is on my old macbook which is kind of slow. However, this function can't be too computationally expensive since anything passed in to id gives that same thing back (not to mention that it's eating up no CPU time). What am I doing wrong?

Opec

The prank answer is "fix has no real use, it's just there so you can type fix error in ghci and feel good about yourself." – Reciprocation

@TomMD - Funny. I'll remember that if anyone ever asks me what fix does and I'm feeling ornery. :-) – Opec

I usually write fix as fix f = f (fix f). Short, simple, works, and identical to the mathematical definition. – Owenowena

@newacct, yeah it's how I think of it too. But the one here can lead to more efficient structures. You can see the difference if you evaluate, say, fix (1:) !! (10^8). The original does it in constant memory, yours takes linear memory (which makes it quite a bit slower, too). That is, using the let "ties a tighter knot", and allows a circular data structure to be generated, whereas yours does not. – Diagnostics

You could have re-invented fix too! helped me understand fix a lot. – Eloyelreath

@fredoverflow's link is the BEST explanation. All the rest confuses me. – Tufts

Answer 1

You are doing nothing wrong. fix id is an infinite loop.

When we say that fix returns the least fixed point of a function, we mean that in the domain theory sense. So fix (\x -> 2*x-1) is not going to return 1, because although 1 is a fixed point of that function, it is not the least one in the domain ordering.

I can't describe the domain ordering in a mere paragraph or two, so I will refer you to the domain theory link above. It is an excellent tutorial, easy to read, and quite enlightening. I highly recommend it.

For the view from 10,000 feet, fix is a higher-order function which encodes the idea of recursion. If you have the expression:

let x = 1:x in x

Which results in the infinite list [1,1..], you could say the same thing using fix:

fix (\x -> 1:x)

(Or simply fix (1:)), which says find me a fixed point of the (1:) function, IOW a value x such that x = 1:x... just like we defined above. As you can see from the definition, fix is nothing more than this idea -- recursion encapsulated into a function.

It is a truly general concept of recursion as well -- you can write any recursive function this way, including functions that use polymorphic recursion. So for example the typical fibonacci function:

fib n = if n < 2 then n else fib (n-1) + fib (n-2)

Can be written using fix this way:

fib = fix (\f -> \n -> if n < 2 then n else f (n-1) + f (n-2))

Exercise: expand the definition of fix to show that these two definitions of fib are equivalent.

But for a full understanding, read about domain theory. It's really cool stuff.

Diagnostics

Here's a related way to think about fix id: fix takes a function of type a -> a and returns a value of type a. Because id is polymorphic for any a, fix id will have the type a, i.e. any possible value. In Haskell, the only value which can be any type is bottom, ⊥, and is indistinguishable from a non-terminating computation. So fix id produces exactly what it should, the bottom value. A danger of fix is that if ⊥ is a fixed point of your function, then it is by definition the least fixed point, therefore fix won't terminate. – Fernandes

@JohnL in Haskell undefined is also a value of any type. You can define fix as: fix f = foldr (\_ -> f) undefined (repeat undefined). – Karli

@Diego your code is equivalent to _Y f = f (_Y f). – Niel

Answer 2

I don't claim to understand this at all, but if this helps anyone...then yippee.

Consider the definition of fix. fix f = let x = f x in x. The mind-boggling part is that x is defined as f x. But think about it for a minute.

x = f x

Since x = f x, then we can substitute the value of x on the right hand side of that, right? So therefore...

x = f . f $ x -- or x = f (f x)
x = f . f . f $ x -- or x = f (f (f x))
x = f . f . f . f . f . f . f . f . f . f . f $ x -- etc.

So the trick is, in order to terminate, f has to generate some sort of structure, so that a later f can pattern match that structure and terminate the recursion, without actually caring about the full "value" of its parameter (?)

Unless, of course, you want to do something like create an infinite list, as luqui illustrated.

TomMD's factorial explanation is good. Fix's type signature is (a -> a) -> a. The type signature for (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) is (b -> b) -> b -> b, in other words, (b -> b) -> (b -> b). So we can say that a = (b -> b). That way, fix takes our function, which is a -> a, or really, (b -> b) -> (b -> b), and will return a result of type a, in other words, b -> b, in other words, another function!

Wait, I thought it was supposed to return a fixed point...not a function. Well it does, sort of (since functions are data). You can imagine that it gave us the definitive function for finding a factorial. We gave it a function that dind't know how to recurse (hence one of the parameters to it is a function used to recurse), and fix taught it how to recurse.

Remember how I said that f has to generate some sort of structure so that a later f can pattern match and terminate? Well that's not exactly right, I guess. TomMD illustrated how we can expand x to apply the function and step towards the base case. For his function, he used an if/then, and that is what causes termination. After repeated replacements, the in part of the whole definition of fix eventually stops being defined in terms of x and that is when it is computable and complete.

Haight

Thanks. This is a very useful and practical explanation. – Maryellen

Love this explanation <3 – Dowson

Answer 3

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
--> id x
--> id (id x)
--> id (id (id 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. First of all, your first fix argument should usually be a function which is the 'recurse' case and the second argument is the data on which to act. Here is the same code as a named function:

getQ h
      | pred h = getQ (mutate h)
      | otherwise = h

If you're still confused then perhaps factorial will be an easier example:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 5 -->* 120

Notice the evaluation:

fix (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) 3 -->
let x = (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x in x 3 -->
let x = ... in (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 3 -->
let x = ... in (\d -> if d > 0 then d * (x (d-1)) else 1) 3

Oh, did you just see that? That x became a function inside our then branch.

let x = ... in if 3 > 0 then 3 * (x (3 - 1)) else 1) -->
let x = ... in 3 * x 2 -->
let x = ... in 3 * (\recurse d -> if d > 0 then d * (recurse (d-1)) else 1) x 2 -->

In the above you need to remember x = f x, hence the two arguments of x 2 at the end instead of just 2.

let x = ... in 3 * (\d -> if d > 0 then d * (x (d-1)) else 1) 2 -->

And I'll stop here!

Reciprocation

Your answer is what actually made fix make sense to me. My answer largely depends on what you have already said. – Haight

@Thomas both your reduction sequences are incorrect. :) id x just reduces to x (which then reduces back to id x). -- Then, in the 2nd sample (fact), when the x thunk is first forced, the resulting value is remembered and reused. The recalculation of (\recurse ...) x would happen with non-sharing definition y g = g (y g), not with this sharing fix definition. -- I've made the trial edit here - you're welcome to use it, or I could make the edit if you approve. – Niel

actually, when fix id is reduced, let x = id x in x also forces the value of application id x inside the let frame (thunk), so it reduces to let x = x in x, and this loops. Looks like it. – Niel

Correct. My answer is using equational reasoning. Showing the reduction a la Haskell, which concerns itself with evaluation order, only serves to confuse the example without any true gain. – Reciprocation

The question is tagged with both haskell and letrec (i.e. the recursive let, with sharing). The distinction between fix and Y is very clear and important in Haskell. I don't see what good is served by showing the wrong reduction order when the correct one is even shorter, much clearer and easier to follow, and reflects correctly what actually is going on. – Niel

This real example is really useful. One can use it as a template for decomposing a recursive algorithm into pred and mutate components, which makes it straightforward to convert mathematical definitions of recursive sequences or even inductive proofs to Haskell code. – Venous

Answer 4

How I understand it is, it finds a value for the function, such that it outputs the same thing you give it. The catch is, it will always choose undefined (or an infinite loop, in haskell, undefined and infinite loops are the same) or whatever has the most undefineds in it. For example, with id,

λ <*Main Data.Function>: id undefined
*** Exception: Prelude.undefined

As you can see, undefined is a fixed point, so fix will pick that. If you instead do (\x->1:x).

λ <*Main Data.Function>: undefined
*** Exception: Prelude.undefined
λ <*Main Data.Function>: (\x->1:x) undefined
[1*** Exception: Prelude.undefined

So fix can't pick undefined. To make it a bit more connected to infinite loops.

λ <*Main Data.Function>: let y=y in y
^CInterrupted.
λ <*Main Data.Function>: (\x->1:x) (let y=y in y)
[1^CInterrupted.

Again, a slight difference. So what is the fixed point? Let us try repeat 1.

λ <*Main Data.Function>: repeat 1
[1,1,1,1,1,1, and so on
λ <*Main Data.Function>: (\x->1:x) $ repeat 1
[1,1,1,1,1,1, and so on

It is the same! Since this is the only fixed point, fix must settle on it. Sorry fix, no infinite loops or undefined for you.

Globin

Answer 5

As others pointed out, fix somehow captures the essence of recursion. Other answers already do a great job at explaining how fix works. So let's take a look from another angle and see how fix can be derived by generalising, starting from a specific problem: we want to implement the factorial function.

Let's first define a non recursive factorial function. We will use it later to "bootstrap" our recursive implementation.

factorial n = product [1..n]

We approximate the factorial function by a sequence of functions: for each natural number n, factorial_n coincides with factorial up to and including n. Clearly factorial_n converges towards factorial for n going towards infinity.

factorial_0 n = if n == 0 then 1 else undefined
factorial_1 n = n * factorial_0(n - 1)
factorial_2 n = n * factorial_1(n - 1)
factorial_3 n = n * factorial_2(n - 1)
...

Instead of writing factorial_n out by hand for every n, we implement a factory function that creates these for us. We do this by factoring the commonalities out and abstracting over the calls to factorial_[n - 1] by making them a parameter to the factory function.

factorialMaker f n = if n == 0 then 1 else n * f(n - 1)

Using this factory, we can create the same converging sequence of functions as above. For each factorial_n we need to pass a function that calculates the factorials up to n - 1. We simply use the factorial_[n - 1] from the previous step.

factorial_0 = factorialMaker undefined
factorial_1 = factorialMaker factorial_0
factorial_2 = factorialMaker factorial_1
factorial_3 = factorialMaker factorial_2
...

If we pass our real factorial function instead, we materialize the limit of the series.

factorial_inf = factorialMaker factorial

But since that limit is the real factorial function we have factorial = factorial_inf and thus

factorial = factorialMaker factorial

Which means that factorial is a fixed-point of factorialMaker.

Finally we derive the function fix, which returns factorial given factorialMaker. We do this by abstracting over factorialMaker and make it an argument to fix. (i.e. f corresponds to factorialMaker and fix f to factorial):

fix f = f (fix f)

Now we find factorial by calculating the fixed-point of factorialMaker.

factorial = fix factorialMaker

Zendah