Looking at the GHC source code I can see that the definition for fix is:
fix :: (a -> a) -> a
fix f = let x = f x in x
In an example fix is used like this:
fix (\f x -> let x' = x+1 in x:f x')
This basically yields a sequence of numbers that increase by one to infinity. For this to happen fix must be currying the function that it receives right back to that very function as it's first parameter. It isn't clear to me how the definition of fix listed above could be doing that.
This definition is how I came to understand how fix works:
fix :: (a -> a) -> a
fix f = f (fix f)
So now I have two questions:
- How does x ever come to mean fix x in the first definition?
- Is there any advantage to using the first definition over the second?
It's easy to see how this definition works by applying equational reasoning.
What will
x
evaluate to when we try to evaluatefix f
? It's defined asf x
, sofix f = f x
. But what isx
here? It'sf x
, just as before. So you getfix f = f x = f (f x)
. Reasoning in this way you get an infinite chain of applications off
:fix f
=f (f (f (f ...)))
.Now, substituting
(\f x -> let x' = x+1 in x:f x')
forf
you getEdit: Regarding your second question, @is7s pointed out in the comments that the first definition is preferable because it is more efficient.
To find out why, let's look at the Core for
fix1 (:1) !! 10^8
:As you can see, after the transformations
fix1 (1:)
essentially becamemain_x = 1 : main_x
. Note how this definition refers to itself - this is what "tying the knot" means. This self-reference is represented as a simple pointer indirection at runtime:Now let's look at
fix2 (1:) !! 100000000
:Here the
fix2
application is actually preserved:The result is that the second program needs to do allocation for each element of the list (but since the list is immediately consumed, the program still effectively runs in constant space):
Compare that to the behaviour of the first program: