The fix function, available in GHC’s base package within the Data.Function module, encapsulates the concept of recursion. Most usefully, it allows us to make anonymous functions recursive. The easiest way to explain fix is simply to reinvent it.

Once More, from the Bottom

Consider the “normal” factorial function:

fact :: Integer -> Integer
fact 0 = 1
fact n = n * fact (n - 1)

We can’t write this as an anonymous function because it’s recursive, so let’s refactor it into a non-recursive version:

nonrecFact :: (Integer -> Integer) -> Integer -> Integer
nonrecFact _ 0 = 1
nonrecFact rec n = n * rec (n - 1)

All we’ve done is give the recursive call a different name and make it a parameter. Unforunately, nonrecFact is somewhat harder to use than the original fact. Here’s what happens when we try to apply nonrecFact to itself:

> fact 5
6
> nonrecFact nonrecFact 5
<interactive>:0:12:
    Couldn't match expected type `Integer'
                with actual type `Integer -> Integer'
    Expected type: Integer -> Integer
      Actual type: (Integer -> Integer) -> Integer -> Integer
    In the first argument of `nonrecFact', namely `nonrecFact'
    In the expression: nonrecFact nonrecFact 5

GHC is reminding us that the first argument to nonrecFact should have the type Integer -> Integer, but that nonrecFact doesn’t have that type, so nonrecFact nonrecFact 5 doesn’t have a valid type. We can try again with nonrecFact (nonrecFact nonrecFact) 5 or nonrecFact (nonrecFact (nonrecFact nonrecFact)) 5, but we’ll always get the same type error because the right-most nonrecFact isn’t applied to any arguments.

To make it typecheck (and get the factorial function we’re after), we’d have to apply nonrecFact to itself infinitely many times. That might sound ridiculous if you’re coming from an eagerly-evaluated language, but Haskell makes it easy:

makeRec :: (a -> a) -> a
makeRec f = f (makeRec f)

Take a moment to convince yourself that the type of makeRec is correct—that is, that the input and output types of f must be the same for this to work.

Now we can use our nonrecursive factorial function and get real answers:

> makeRec nonrecFact 5
120

Our goal from the start was to define factorial using an anonymous function, so let’s do it:

> let anonFact = makeRec $ \rec n -> if n == 0 then 1 else n * rec (n - 1)
> anonFact 5
120

Back to Reality

The big secret, if you haven’t already guessed it, is that makeRec and fix are one and the same. Here are a couple more examples:

> let mapfix = fix $ \rec f xs -> if null xs then [] else f (head xs) : rec f (tail xs)
> mapfix ((^2) . (+2)) [1..5]
[9, 16, 25, 36, 49]
>
> let reversefix = \xs -> fix (\rec old new -> if null old then new else rec (tail old) (head old : new)) xs []
> reversefix [1..5]
[5,4,3,2,1]

TL;DR: To make an anonymous function recursive using fix, include the recursively called function as the first parameter.

Further Reading

From a pragmatic standpoint, there isn’t much more to fix than I’ve shown you here. There is, however, some interesting type theory that comes with a more academic discussion of it. For those interested, I’d recommend starting with the Fix and recursion page of the Haskell wikibook.