The Haskell School of Expression: Exercises

fix f = f (fix f)

First, f takes the result of fix f, and second, the return type of f must be the same as the return type of fix.

fix :: (a -> a) -> a

Research shows that fix is the Fixed point combinator (or Y-combinator). Apparently this allows the definition of anonymous recursive functions. So let’s try to make remainder into an anonymous function. A good way to start is to simply remove one of the arguments and see if we can return an anonymous function. Something tells me that a is the argument to remove, since b is used in the base case.

remanon b = (\f x -> if x < b then x
                     else f (x-b))

That’s a good start. Note here that if we try to do something like:

(remanon 3) remanon

Haskell says “unification would give infinite type” – which is a good sign. This is what we would like to do with the help of fix. So now if we apply fix to this, we get:

fix (remanon b)
= (remanon b) (fix (remanon b))
= (\x -> if x < b then x
         else (fix (remanon b)) (x-b))

Which looks good. So we need to fix remanon and apply it to a.

remainder' a b = fix (remanon b) a

And that works.

This entry was posted on Wednesday, August 8th, 2007 at 11:52 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.