`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.

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 ; [] -> [] }

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 (letzeroes = 0 : zeroesinzeroes)

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.

letzeroes = 0 : zeroesinzeroesletfibs = 0 : scanl (+) 1 fibsinfibsletfactorial = \n -> if n==0 then 1 else n * factorial(n-1)infactorialletmapeven = \case { n:ns -> even n : mapeven ns ; [] -> [] }inmapeven

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:

letx = 0 : xinxletx = 0 : scanl (+) 1 xinxletx = \n -> if n==0 then 1 else n * x(n-1)inxletx = \case { n:ns -> even n : x ns ; [] -> [] }inx

Notice how the above recursive `let`

-expressions fall under
a common theme:

letx = ... x ...inx

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:

letx = (\v -> 0 : v) xinxletx = (\v -> 0 : scanl (+) 1 v) xinxletx = (\v -> \n -> if n==0 then 1 else n * v(n-1)) xinxletx = (\v -> \case { n:ns -> even n : v ns ; [] -> [] }) xinx

The theme is even clearer: It looks like

letx = f xinx

where `f`

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

:

fix f =letx = f xinx

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.

`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