beginner's questions - fix f

[Andreas Rossberg]

Bob Koutsky wrote:
> 
> 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.

Function fix is a so-called fixpoint operator. Theory says that you can
formulate any computable function using only non-recursive definitions
plus fix.

> Can somebody provide me
> with an example how to use fix for something just a bit useful, if possible
> to rewrite remainder?

Try:

remainderF self a b = if a < b then a else self (a-b) b

remainder = fix remainderF

From this example it is easy to infer how to transform arbitrary
recursive definitions. Even generalising it to mutual recursion is not
difficult (and left as an exercise to the reader ;-).

All the best,

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids.
 If Pac Man affected us as kids, we would all be running around in
 darkened rooms, munching pills, and listening to repetitive music."