The Fixed Point

Getting To The (Fixed) Point

Haskell offers ample opportunities for ah ha! moments, where figuring out just how some function or feature works can unlock a whole new way of thinking about how you write programs. One great example of an ah-ha moment comes from when you can first start to understand fixed points, why you might want to use them, and how exactly they work in haskell. In this post, you’ll work through the fixed point function in haskell, building several examples along the way. At the end of the post you’ll come away with a deeper understanding of recursion and how haskell’s lazy evaluation changes the way you can think about writing programs.

If you already have some experience with haskell, you may want to skip the first section and jump directly into learning about fix

Update: 2021-06-13: A reader has submitted a PR to fix a few typos.

A Quick Look at Recursion in Haskell

A recursive function is a function that refers back to itself. There are different ways that you can accomplish recursion, and throughout this article we’ll look at several of them. We’ll start by defining a couple of new terms to help us differentiate some particular aspects of recursion that will matter as we’re exploring fixed points: manual recursion, automatic recursion, and recursive bindings. Throughout this section of the article we’ll spend some time with each of these types of recursion, building up some examples and working our way towards a better understanding of how they let us think about the general nature of recursion and how it relates to fixed points.

Manual Recursion

We’ll start our investigation of recursion by thinking about manual recursion. When you are first learning haskell, manual recursion is probably the thing you think about when you think about the word recursion. We call it manual recursion because it occurs when you, the programmer, directly make a recursive call back to the function you are currently writing.

Let’s look at a classic example of recursion written in a directly recursive style. We’ll start by writing a factorial function. If you’re not familiar with factorial, it’s a function that when given 0, returns 1. When given a number greater than 0, n, it gives you the result of multiplying all of the numbers from 1 to n. For example:

factorial 5 = 1 * 2 * 3 * 4 * 5 = 120

To make things a bit easier on ourselves in the next step, let’s think about the factorial function as counting down from our input number, instead of counting up toward it, so we can say:

factorial 5 = 5 * 4 * 3 * 2 * 1 = 120

The first thing we need to do is to think about how we can take our factorial function and break it down into increasingly smaller pieces that have the same shape as our overall function. Whenever we’re writing a recursive function, it helps to start by looking at how we can reframe the problem in terms of something getting smaller.

One way to see how we can break factorial down into smaller pieces is to notice that:

factorial 5 = 5 * 4 * 3 * 2 * 1
factorial 4 =     4 * 3 * 2 * 1

So we can rewrite factorial 5 to say:

factorial 5 = 5 * (4 * 3 * 2 * 1)
            = 5 * (factorial 4)

If we go one more step, we can see that:

factorial 4 = 4 * (3 * 2 * 1)
factorial 3 =     (3 * 2 * 1)

factorial 4 = 4 * (factorial 3)

From these examples you can start to see the shape of the recursive function that we’ll be writing, and how the sub-problem that we are solving at each step gets a little bit smaller.

The next thing we want to think about before we write a recursive function is when we should stop. This is called the base case. For our factorial function, the base case is the smallest number that we can calculate a factorial for, which is 0 and that’s given to us by the definition of factorial.

With that information in hand, we can write our factorial function using direct recursion.:

factorial :: Integer -> Integer
factorial n =
  case n of
    0 -> 1
    n -> n * (factorial (n - 1))

Automatic Recursion

Unlike manual recursion, where we can see the recursive structure of our function by looking for the place in our code where a function calls itself, a function that is using automatic recursion does so indirectly, using a function that manages the recursion for us automatically.

One example of automatic recursion that you’re likely familiar with are the fold functions: foldl and foldr. These two functions, and others like them, allow you to work on data that can naturally be traversed recursively while only having to implement the code to deal with the current element and any state that you want to carry over across calls.

We can use a function like foldr to write a factorial by letting it do the recursion for us:

factorial :: Integer -> Integer
factorial n =
  let
    handleStep currentNum currentFact =
      currentNum * currentFact
  in foldr handleStep 1 [1..n]

Even if you’ve used foldr before, it will be helpful as we’re framing the problem to build a version of it ourselves, so that we can think through how these sorts of recursive functions work.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f accum items =
  case items of
    [] ->
      accum
    (next:rest) ->
      f next (foldr f accum rest)

Looking at this function, you can see how the shape of the function, with the case statement, the base case with an empty list, and the recursive call that each time moves one element forward in the list. Our implementation of foldr is more generic to be sure- we’ve replaced the knowledge that factorial 0 is 1 with a more general statement that the value of our fold at our base case is the initial accumulator value that was provided, and now instead of doing multiplication directly in our recursive call we hand off the details to a function that is passed in, but if you squint a bit you can see how similar the two functions really are.

Using functions like folds that deal with the shape of the data and handle the recursion for us has a number of benefits. First, it removes some unnecessary duplication of code. Traversing data structures and doing something on all of the elements is quite common in functional programming, and if we were to implement it from scratch each time it would take us much longer to write programs, and there are many more opportunities for errors. Second, it makes our code a bit more readable by letting us center the “business logic” of our function. In most cases, the fact that our data is represented as a list, a binary tree, etc. is incidental to the problem at hand. By separating out the logic for dealing with individual elements from the logic for traversing data structures, we center the relevant bits of our code. Finally, and perhaps most importantly, functions like folds give us a common language for talking about the structure of our programs. For someone who has been programming for some time, saying that something is “simply a fold over some data” can convey a good deal of information about the general idea of how a program is implemented without the need to bog them down in too many extraneous details.

Recursive Let Bindings

The final type of recursion we’ll look at in this first section is not so much a specific technique to do recursion as it is a feature of haskell that allows you to use manual recursion more easily: recursive let bindings.

Haskell’s recursive let bindings mean that you can use recursion inside of a let expression in your function. A simple example of this would be, continuing with our factorial example, a function that computers the double factorial, that is to say, the factorial of the factorial of an input number:

-- Note: This function grows very quickly.
--   doubleFactorial 5 is a 199-digit number
--   doubleFactorial 8 is a 168187-digit number
doubleFactorial :: Integer -> Integer
doubleFactorial n =
  let
    factorial a =
      case a of
        0 -> 1
        a -> a * factorial (a - 1)
  in factorial (factorial n)

Fixing Functions

The fix function, defined in Data.Function in basegives us another way to approach recursion in haskell. Let’s start by taking a look at the documentation for fix:

Fix By The Docs

For ease of readability, the documentation for fix is reproduced below:

fix fis the least fixed point of the function f, i.e. the least defined x such that f x = x.

For example, we can write the factorial function using direct recursion as

λ let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5
120

This uses the fact that Haskell’s let introduces recursive bindings. We can rewrite this definition using ‘fix’,

λ fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5
120

Instead of making a recursive call, we introduce a dummy parameter rec; when used within fix, this parameter then refers to fix’s argument, hence the recursion is reintroduced. fix :: (a -> a) -> a

Untangling the Type of fix

Whenever we want to understand something new in haskell, a good first instinct is to start by looking at the types, as this tells us quite a bit about what a function can, and often more importantly can’t do.

The type of fix :: (a -> a) -> a tells us that it’s going to take a function, and return a value. For the sake of discussion, let’s give the function that we pass into fix the nameg. So, g :: a -> a and fix g :: a.

At first look, this might not look all that difficult at all. fix just needs to call g with a value to get a value back out that it can return. We can imagine any number of similar functions that would work for some specific type, an Int:

applyZero :: (Int -> Int) -> Int
applyZero g = g 0

Similarly, we can think of any number of candidates for g that we could pass in and get a good result back out:

λ applyZero (+1)
1
λ applyZero (*4)
0

Unfortunately, this relies on the fact that applyZero can pick some number to pass in. It can do that because we know that it’s working with Int values, so we can pick an Int value to pass into it. fix doesn’t have things so easy- since a could be anything there’s no value we can pick to pass into g to get back a value.

We can see this play out if we try to pass some function, like (+1) into fix: It will never give us back a value, because it can’t. You can try it yourself in ghci. When you are satisfied that you won’t get back a value, you can type control+c to cancel the current function.

λ fix (+1)
Interrupted.

The trick to fix is that, sometimes, it can give back a result. It can do that when the final value that you get back out doesn’t depend on any particular input value. For example, if we use the const function, which ignores any argument passed into it and just returns a value, then we can get a result from fix:

λ fix (const "hello, haskell")
"hello, haskell"

Ignoring the question of how this could possibly work, it makes sense. The definition of a fixed point of a function is that it’s a value that, when passed into a function, causes the function to return that same value. This is exactly what const does- ignores its input and returns some value:

λ :t const
const :: a -> b -> a
λ :t const "foo"
const "foo" :: b -> [Char]
λ f = const "foo"
λ f 1
"foo"

This means that whatever value we pass into const will be the fixed point of the function that it returns.

Outside of the mathematical definition of a fixed point, the behavior of fix also makes sense if we think about it in terms of laziness, and computability. We’ve already noted that because the fix is polymorphic, fixed itself can’t ever get a value to pass into the function it’s trying to find the fixed point of. In a strictly evaluated language, that would be a problem, but thanks to haskell’s laziness, “a value we can’t ever actually compute” is still something that we can work with.

In the case of fix, the parameter that it passes into its function might be a value that we can’t ever actually compute, but it turns that that’s actually perfectly okay so long as we never try to compute it. In other words, if the function we pass in is lazy in its argument, then we never try to run the impossible calculation of creating a value, and so everything works out.

The Two-Argument Conundrum

Now that you understand how fix can take advantage of laziness to work at all, there’s another aspect to fix that might trip you up reading through the documentation. Recall that the type of fix is fix :: (a -> a) -> a, but what the documentation passes in a factorial function that takes two arguments:

λ fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5
120

We can factor the function out from this example and give it a name, and confirm that it does, in fact, take two arguments: rec, a function with type (p -> p), and n, a value of type p.

λ factorial = \rec n -> if n <= 1 then 1 else n * rec (n-1)
λ :t factorial
factorial :: (Ord p, Num p) => (p -> p) -> p -> p

So that it’s a bit easier for us to talk about, let’s pick some specific type to use as we’re thinking about this. For no particular reason, let’s use Int, so we can let factorial have the type:

factorial :: (Int -> Int) -> Int -> Int

There are two things that we need to remember to be able to put together how this works. The first is that it can sometimes be quite helpful for us to stop and remember that haskell functions are curried, and to think through what our type signatures really mean when we look at them.

We might naturally read the type (Int -> Int) -> Int -> Int as a function that takes a function from an Int to an Int, and an Int, returning an Int. Most of the time we can get by just fine when we read our function types this way, but every once in a while it can throw us for a loop.

Since haskell functions are curried, a we can rewrite a function like:

factorial :: (Int -> Int) -> Int -> Int
factorial = \rec n -> if n <= 1 then 1 else n * rec (n-1)

Into one that takes a single argument and returns a new function:

factorial :: (Int -> Int) -> Int -> Int
factorial = \rec -> \n -> if n <= 1 then 1 else n * rec (n-1)

When we rewrite it that way, we might naturally want to describe the function as: a function that takes a function from and Int to an Int, and returns a function from an Int to an Int. We can rewrite our type signature to reflect this restatement of our function so that it reads:

factorial :: (Int -> Int) -> (Int -> Int)
factorial = \rec -> \n -> if n <= 1 then 1 else n * rec (n-1)

Looking at this rewritten type signature now, we can start to see the second important thing that we need to keep in mind. When we’re dealing with polymorphic functions that take an a, the a could be anything, including a function. If we replace the a type parameters with (Int -> Int) then the type of fix would become:

fixFactorial :: ((Int -> Int) -> (Int -> Int)) -> (Int -> Int)

Or, if we let ghci render the type for us without any unnecessary parentheses:

fix @(Int -> Int) :: ((Int -> Int) -> Int -> Int) -> Int -> Int

In the next section we’ll take a look at how fix is actually implemented. Once you’ve had a chance to see the implementation, we’ll come back to both the type of fix and how it works with laziness and put all of that knowledge together into a more cohesive understanding of how it actually works.

Implementing fix

For all of the discussion about how fix works, its implementation is remarkably short. Whenever we find ourselves facing something completely unknown in haskell, we can start by looking at the types, and the next step is often to read the source code. The source code for fix is available on hackage, and it’s quite short:

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

Let’s walk through what’s happening here and see if we can get a handle on it. We start with a parameter, f, which is whatever function we want to find the fixed point for.

Next, we create a recursive let binding where we define x to be the result of applying f to x. This recursive let binding is the magic behind how the fixed point calculation works.

When we first call fix and create the let binding where we define x, we know that it has to have the type a, and a value that, when it’s needed, will be computed by the expression f x.

The x in that computation, likewise, isn’t a value yet. It’s a thunk that, if it is evaluated, will be computed by calling f x. In other words, we start with:

fix f = let x = {- <some unevaluated thunk> -} in x

If whoever calls this function decides they need the value of x, then they’ll get:

fix f = let x = f {- <some unevaluated thunk> -} in x

If f is a function like const that always returns a value without ever looking at its input value, then x will get set to that value and can be evaluated without any issues at all.

On the other hand, if f does need to evaluate x, like when we tried to pass in (+1), we’ll end up with a computation that can never complete, because each time we try to look at x we’ll get back another layer of some unevaluated thunk. On the surface, this might seem to be a bit limited. After all, if we need to pass in a function that always returns a value and never looks at its input, we’re limited to permutations of const and not much else, unless we can get some data to work with from somewhere else…

Tying The Knot

The fix function doesn’t require a function that never evaluates its argument in order to eventually give us back a value. Instead, we need to give it a function that eventually doesn’t evaluate its argument. The one-word difference here between never and eventually is the difference between a computation that terminates and is well-defined, and one that is undefined. This is where passing a function of two parameters into fix comes into play. When we have a function like (Int -> Int) there’s no option except for the input value that we’re given to decide when to terminate, so we always have to evaluate it. On the other hand, a function with the type (Int -> Int) -> (Int -> Int) has much more flexibility. To see how, let’s go back to our definition of factorial:

factorial :: (Int -> Int) -> (Int -> Int)
factorial rec = \n -> if n <= 1 then 1 else n * rec (n-1)

In this factorial function, we’re taking a parameter, rec :: Int -> Int, but we only ever evaluate it if n is greater than 1. Since n decreases with each step, we know that it will eventually reach 1 (assuming we started with a positive number), and so we know that rec will eventually not be evaluated, and we can return a good value.

When we look at this deeply we can see that this is actually a really interesting approach- we’re taking advantage of laziness so that we can return a function that only causes a value in its closure to be evaluated when the input to the returned function is sufficiently high. It’s almost like we’re passing information backwards through time, but in fact we’re simply making use of the behavior of lazy evaluation and the call stack to propagate information back and eventually resolve some thunks that have been hanging out patiently waiting around for us to allow them to be computed.

As a final exercise, let’s walk through the example step by step to get a much better idea of what’s happening when we make use of fix.

Fixing The Factorial

We’ll start our manual evaluation by defining two functions:

factorial' :: (Int -> Int) -> (Int -> Int)
factorial' rec = \n -> if n <= 1 then 1 else n * rec (n-1)

factorial :: Int -> Int
factorial = fix factorial'

In ghci we’ll start by calling factorial with 5:

λ factorial 5

We can expand this to:

fix (\rec n -> if n <= 1 then 1 else n * rec (n - 1)) 5

And that, in turn, becomes:

let x = (\rec n -> if n <= 1 then 1 else n * rec (n - 1)) x in x 5

If we apply this function to 5, and replace n with 5 we end up with:

let x = (\rec 5 ->
  if 5 <= 1 then 1 else 5 * rec (5 - 1)
  ) x
in x 5

Following the pattern until we get to our base case, we have:

  let x = (\rec 5 ->
             if 5 <= 1 then 1 else 5 * rec (5 - 1)
          ) $ (\rec' 4 ->
             if 4 <= 1 then 1 else 4 * rec' (4 - 1))
          ) $ (\rec'' 3 ->
             if 3 <= 1 then 1 else 3 * rec'' (3 - 1))
          ) $ (\rec''' 2 ->
             if 2 <= 1 then 1 else 2 * rec''' (2 - 1))
          ) $ (\_rec 1 ->
             if 1 <= 1 then 1 else {- never evaluated #-}
          )
  in x $ 5

Once we finally hit the case where n == 1 and we stop evaluating rec we can start to resolve the stack of calls in reverse order, so rec''' becomes 1 and we get:

  let x = (\rec 5 ->
             if 5 <= 1 then 1 else 5 * rec (5 - 1)
          ) $ (\rec' 4 ->
             if 4 <= 1 then 1 else 4 * rec' (4 - 1))
          ) $ (\rec'' 3 ->
             if 3 <= 1 then 1 else 3 * rec'' (3 - 1))
          ) $ (\rec''' 2 ->
             if 2 <= 1 then 1 else 2 * 1)
          )
  in x $ 5

Which becomes:

  let x = (\rec 5 ->
             if 5 <= 1 then 1 else 5 * rec (5 - 1)
          ) $ (\rec' 4 ->
             if 4 <= 1 then 1 else 4 * rec' (4 - 1))
          ) $ (\rec'' 3 ->
             if 3 <= 1 then 1 else 3 * 2
          )
  in x $ 5

And so on until we finally get to:

  let x = (\_ 5 ->
             if 5 <= 1 then 1 else 5 * 4 * 3 * 2
          )
  in x $ 5

Conclusion

In this post you’ve learned how the fix function from Data.Function relies on important features of haskell, like laziness and recursive let bindings, to provide us with a way of doing automatic recursion without having to ever directly make a recursive call. By understanding how haskell’s type system, currying, and lazy evaluation work together, and taking time to sympathize with the compiler and better understand how expressions are evaluated, you can start to see precisely how some of the more interesting, and at first more intimidating, areas of haskell work.