Search code examples
haskellfixpoint-combinators

Why is this version of 'fix' more efficient in Haskell?

In Haskell, this is a simple (naive) definition of a fixed point

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

But, here is how Haskell actually implements it (more efficient)

fix f = let x = f x in x

My question is why is the second one more efficient than the first?

Solution

  • The slow fix calls f on each step of recursion, while the fast one calls f exactly once. It can be visualized with tracing:

    import Debug.Trace

fix  f = f (fix f)
fix' f = let x = f x in x

facf :: (Int -> Int) -> Int -> Int
facf f 0 = 1
facf f n = n * f (n - 1)

tracedFacf x = trace "called" facf x

fac  = fix tracedFacf
fac' = fix' tracedFacf

    Now try some running:

    > fac 3
called
called
called
called
6
> fac' 3
called
6

    In more detail, let x = f x in x results in a lazy thunk being allocated for x, and a pointer to this thunk is passed to f. On first evaluating fix' f, the thunk is evaluated and all references to it (here specifically: the one we pass to f) are redirected to the resulting value. It just happens that x is given a value that also contains a reference to x.

    I admit this can be rather mind-bending. It's something that one should get used to when working with laziness.