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."