beginner's questions - fix f

[Lars Henrik Mathiesen]

> From: Bob Koutsky <bck@webhome.cz>
> Date: Tue, 24 Jul 2001 09:49:33 +0200
> 
> [...] suddenly, I hit a wall:
> 
> ------------------------------------------------------------
> Exercise 9.9:
> remainder a b = if a < b then a
>                          else remainder (a-b) b
> 
> fix f = f (fix f)
> 
> Rewrite remainder using fix so that it is not recursive.
> ------------------------------------------------------------
> 
> Function fix left me completely puzzled. With help of hugs I found out that 
> its type is "( a -> a ) -> a", but I have absolutely no idea how it could 
> be used to do anything useful. It seems to me that argument to f on the 
> right side of fix's definition must always evaluate to the same value, no 
> matter how deep the recursion is, so there is no point to use it. I guess I 
> am missing something very obvious, but what is it? Can somebody provide me 
> with an example how to use fix for something just a bit useful, if possible 
> to rewrite remainder?

Well, it is a kind of sleight of hand. The idea is that if you already
had a working remainder function, you could use that to write another,
like this:

     remainder2 a b = if a < b then a
                      else remainder (a-b) b

That's not very interesting. But if you made the 'working' function
into an argument of a 'step' function:

     rem_step f a b = if a < b then a else f (a-b) b

you could actually define remainder like this:

     remainder3 = rem_step remainder3

Now this is still a recursive definition, but it makes it easier to
see how the fix function works in a minute. An example evaluation:

     remainder3 3 2 ==>
     rem_step remainder3 3 2 ==>
     if 3 < 2 then 3 else remainder3 (3-2) 2 ==>
     remainder3 1 2 ==>
     rem_step remainder3 1 2 ==>
     if 1 < 2 then 1 else remainder3 (1-2) 2 ==>
     1

Now, anything that's defined as "x = f x" is called a fixpoint of f.
It's possible to prove that there's only one (when f is a Haskell
function, at least) so we can talk of 'the' fixpoint.

Since we can rewrite all recursive definitions in this form, we could
get rid of all explicit recursion if we had a 'fixpoint operator' that
would solve the equation for us. That operator is usually called
'fix', and since we want "fix f" to be a solution to the equation, we
get the defining equation in your exercise:

     fix f = f (fix f)

This looks like a recursive definition again, but if you want a system
without explicit recursion you have to disallow this as a function. In
such a system, fix is a builtin operator, and the equation can be seen
as a rewrite rule that lets you reason about the evaluation of
expressions that contain it.

However, it turns out that Haskell is quite happy to use the
definition as it stands. Let's redo the example:

     fix f = f (fix f)
     remainder4 = fix rem_step

     remainder4 3 2 ==>
     fix rem_step 3 2 ==>
     rem_step (fix rem_step) 3 2 ==>
     if 3 < 2 then 3 else (fix rem_step) (3-2) 2 ==>
     fix rem_step 1 2 ==>
     rem_step (fix rem_step) 1 2 ==>
     if 1 < 2 then 1 else (fix rem_step) (1-2) 2 ==>
     1

As you noted, each occurence of "fix rem_step" above is in a sense the
same, and could evaluate in the same way. But since the expression is
a function (in this case), how it actually behaves depends on its
arguments --- I think that's really the point you were looking for:
because Haskell is lazy, and there's no structure sharing between the
occurences, each occurence is only expanded as often as necessary.

Note that operationally, this Haskell version of the fixpoint operator
is only sort-of equivalent to a Haskell recursive definition (which is
defined in terms of a 'real' fixpoint). That's even clearer with data
structures; compare

     zeroes = 0 :: zeroes

and

     zer_step l = 0 :: l
     zeroes2 = fix zer_step

zeroes is a circular list with one element, while zeroes2 is an
infinite list with all zero elements. It may not be easy to tell the
difference from inside a Haskell program, but the sound of the disk
thrashing will sometimes alert the programmer to it.

Lars Mathiesen (U of Copenhagen CS Dep) <thorinn@diku.dk> (Humour NOT marked)