The practicality of the ‘fix’ combinator
In Control.Monad.Fix and Data.Function, there is a combinator function called fix. Its type is (a -> a) -> a. It is defined as:
fix f = let x = f x in x
but it could also be defined (maybe more clearly) as:
fix f = f (fix f)
It creates an infinite chain of the function, and it’s sometimes used to rewrite a recursive function. For example:
ones = 1:ones
is equivalent to:
ones = fix (1 :)
Because Haskell is lazy, and (:) doesn’t require evaluation of the right-side to evaluate the left-side, this works and will print in GHCi as [1,1..] would.
Another example is the factorial function:
fact = fix (\fact n -> case n of 0 -> 1; _ | n >= 1 -> n * fact (n - 1))
Thanks to Derek Elkins for the above example
Although understanding how the fix combinator works is a powerful realization (like much of Haskell, really) — it feels like points-free for the sake of points-free to me, when used in actual code. Points-free functions can often make how the functions work clearer, however, there are many cases in which a standard, pattern-matched function would be clearer. The factorial above is easily expressed as:
fact 0 = 1
fact n | n >= 1 = n * fact (n-1)
Although the version using the fixed-point combinator is arguably more beautiful functionally, I opine that the latter version looks better.
There are several more “real-world” applications of fix on the Enumerator and iteratee page of the Haskell wiki. However, I think that even in this case where the fixed-point combinator applies quite nicely, it is still much cleaner and more practical to use simple, tail-call recursive functions.
