You could have re-invented `fix` too!

Albert Y. C. Lai, trebla [at] vex [dot] net

There is too much mysticism and jargon surrounding the `fix` combinator. (OK OK, “combinator” is yet another mystical jargon, don't worry about it.) I want to demystify it by showing how you could have re-invented it yourself.

Recursion

You already know how to write recursive code. We will need recursive code to see the road to `fix`, so here is some.

```zeroes = 0 : zeroes

fibs = 0 : scanl (+) 1 fibs

factorial n = if n==0 then 1 else n * factorial(n-1)

mapeven (n:ns) = even n : mapeven ns
mapeven [] = []
```

Later I will want all of them to uniformly look like name=defn, so two of them need to be rewritten:

```zeroes    = 0 : zeroes

fibs      = 0 : scanl (+) 1 fibs

factorial = \n -> if n==0 then 1 else n * factorial(n-1)

mapeven = \case { n:ns -> even n : mapeven ns ; [] -> [] }
-- Requires LambdaCase extension. The old way is:
--        \tmp -> case tmp of { n:ns -> even n : mapeven ns ; [] -> [] }
```

Anonymous Recursion: Boilerplate

Notice how the above recursive definitions use up names from whatever namespace they live in. If the functions are of great utility and needed by many callers, that is good practice. But sometimes, you may wonder how to write a piece of recursive code without using up a name, perhaps because you use it at only one place, and it is short, and you feel it is OK to “inline” it. Or you wonder about it just for curiosity. You can already inline everything else; can you also inline a recursion?

There is a cheap way: `let`-expressions. Names defined inside a `let`-expression are local and do not use up the enclosing namespace. And although it is not inlining, it is close. Instead of

```zeroes = 0 : zeroes
main = print zeroes
```

you can write

```main = print (let zeroes = 0 : zeroes in zeroes)
```

That puts the recursive code right at the use site, and takes up no name.

Here are more examples; I just show the `let`-expressions, without contexts.

```let zeroes    = 0 : zeroes in zeroes

let fibs      = 0 : scanl (+) 1 fibs in fibs

let factorial = \n -> if n==0 then 1 else n * factorial(n-1) in factorial

let mapeven = \case { n:ns -> even n : mapeven ns ; [] -> [] } in mapeven
```

Of course, by now the names “zeroes”, “fibs”, “factorial”, “mapeven” are local and replaceable. Normally you would choose useful names for them. But I replace them by a useless name to show you a pattern:

```let x = 0 : x in x

let x = 0 : scanl (+) 1 x in x

let x = \n -> if n==0 then 1 else n * x(n-1) in x

let x = \case { n:ns -> even n : x ns ; [] -> [] } in x
```

Anonymous Recursion: Refactored and Reusable

Notice how the above recursive `let`-expressions fall under a common theme:

```let x = ... x ... in x
```

Can you write one single function to capture that theme, so that you can instantiate it with just the “... ...” part? To show how, I rewrite one last time:

```let x = (\v -> 0 : v) x in x

let x = (\v -> 0 : scanl (+) 1 v) x in x

let x = (\v -> \n -> if n==0 then 1 else n * v(n-1)) x in x

let x = (\v -> \case { n:ns -> even n : v ns ; [] -> [] }) x in x
```

The theme is even clearer: It looks like

```let x = f x in x
```

where `f` varies but the rest stays the same. It is only natural to make it a reusable function parameterizing over `f`:

```fix f = let x = f x in x
```

Now all of the above recursive `let`-expressions can be refactored:

```fix (\v -> 0 : v)

fix (\v -> 0 : scanl (+) 1 v)

fix (\v -> \n -> if n==0 then 1 else n * v(n-1))

fix (\v -> \case { n:ns -> even n : v ns ; [] -> [] })
```

As usual, by this point, mature programmers exercise the option of further simplifying that code (and certainly in the third line we can merge the two lambdas). Therefore sometimes you see:

```fix (0 :)

fix ( (0 :) . scanl (+) 1 )

fix (\v n -> if n==0 then 1 else n * v(n-1))

fix (\v -> \case { n:ns -> even n : v ns ; [] -> [] })  -- no change
```

Whether or not to go that far is an eternal debate. But I am showing you how the development goes and how to read it.

As well, you may or may not opine that using `fix` is a good idea: whenever you want to localize a definition, you can choose to stick with a `let`-expression or a `where`-clause, and not go further to `fix`. But I am not defending or advocating it; I am just explaining it.

Why is it called `fix`?

The function is called `fix` because for the equation

```x = f x
```

(considering `x` as an unknown to be solved for) solutions are called fixed points of `f`. They are so called because, as the equation promises, if you plug one of them into `f`, you get it back.

I have more Haskell Notes and Examples