An Introduction to Fixpoint in Haskell
Harold Lee
harold at hotelling.net
Introduction
------------
This is a short article that attempts to explain the concept of
fixpoints to programmers learning the Haskell language. In
particular, it is intended to help people who are stuck trying to
understand the terse discussion of fixpoints in Paul Hudak's
"The Haskell School of Expression" text.
This is a literate Haskell source file, so it can be run - the code
is prefixed with ">" at the beginning of the line.
In Math
-------
"fix" is the fixpoint operator. A fixpoint is a value for which
a function returns the same value. For example, the fixpoint of
> return1 = \x -> 1
is the value 1. return1 only has that one fixpoint, but functions
can have more than one fixpoint, e.g. the identity function has
all values as fixpoints:
> identity = \x -> x
To compute the set of fixpoints of a function (or even just one)
you basically have two options:
1) Perform some sort of search of the domain of the function looking
for fixpoint value(s). The search would likely be guided by
constraining the function space that can be used.
2) Generate a proof based on stepwise algebraic transformation of the
function into a composite of functions with known fixpoints.
In Haskell
----------
Fixpoint behaves differently in Haskell compared to math when defined
as below:
> fix :: (a -> a) -> a
> fix f = f $ fix f
* note that this is the same as writing fix f = f (fix f)
The type is the same as in math: it takes a function from a's to a's
and returns an a (presumably for which f a = a). However, the way in
which Haskell evaluates this definition of fix above is more limited
than the mathematical definition. Basically, it takes a function and
generates an infinite recursion of the function on itself.
The important thing to remember is that Haskell will simply expand
this ad infinitum, but lazily! So if try to compute a fix expansion,
we're typically out of luck:
fix myFunction =
myFunction (fix myFunction) =
myFunction (myFunction (fix myFunction)) =
myFunction (myFunction (myFunction ( ... )))
But if the definition doesn't need to evaluate the (infinitely
recursive) argument, then it is possible to get an answer. This works
for the return1 function above because it ignores the argument:
fix return1 =
(\x -> 1) (fix myFunction) =
the expression 1 with x bound to (fix myFunction) =
1
Note that the last step is possible because the binding of x is not
referenced in the expression. For the identity function defined above,
we're in trouble, because the expanded expression does use the binding
of x. There is no way to find a value for the fix of identity that is
not in terms of the argument.
So (fix return1) is not very interesting because it stops recursively
expanding right away, and (fix identity) is not useful to us because
it recursively expands forever. The trick to using fix for defining
your own recursive functions is to have it expand some number of times
and then start collapsing.
Defining Recursive Functions in Haskell
---------------------------------------
You can use fix to define recursive functions more succinctly using the
pattern that follows.
We'll start with the all-time favorite introductory recursive function,
factorial.
> fact = fix helper
> where helper f x | x <= 1 = 1
> helper f x = x * (f (x-1))
When x is 0 or 1, the expansion of the helper function ends right away,
like it did with (fix return1).
fact 1 =
fix helper 1 =
helper (fix helper) 1 =
the expression 1 with f bound to (fix helper) =
1
When x is larger, then the helper expands using the second pattern,
but it also decreases x with each expansion:
fact 2 =
fix helper 2 =
helper (fix helper) 2 =
2 * (fix helper 1) = * for this step, refer to fact 1 above
2 * 1 =
1
This illustrates the need for laziness in this approach. At each step,
the patterns for the definition of helper are checked, and an appropriate
expansion is selected.
Getting More General
--------------------
We can expand this approach to solve the defining of recursive functions
in general.
The solution is made up of a helper function and the function you're
writing, defined as the fix of the helper. The helper function should
have arguments based on the function you're trying to create, plus an
extra first argument so that it will work with fix.
Applying that approach to the remainder function, which we want to
give the remainder of one number modulo a second number. The type we
want is Haskell is
> remainder :: Integer -> Integer -> Integer
The helper function will need to have an extra argument in the first
position, as well as the two parameters for remainder. We lay out
the base and inductive/recursive step in the helper, and fix does the
rest.
> remainder = fix helper
> where helper f a b | a < b = a
> helper f a b = f (a-b) b
To wrap up, we can define gcd (greatest common divisor) using Euclid's
clever algorithm in a fixpoint calculation. We can use the underscore
(aka don't care) pattern match to make sure we don't accidentally use
the helper's first argument in our base case.
> gcd :: Integer -> Integer -> Integer
> gcd = fix helper
> where helper _ a b | b == 0 = a
> helper f a b = f b (a `remainder` b)
A good next step in understanding how all of this comes together is to
derive the type of the helper function based on the type. of gcd and fix.