You could have re-invented fix too!

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