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.