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

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)