So I am reading Paul Hudak's book "The Haskell School of Expression" and am stuck on an exercise in there.
Here it goes
Suppose function fix is defined as
fix f = f (fix f)
What is the principal type of fix? That one I know, it's b -> b -> b
But I don't understand the way fix is defined, won't it go into an infinite recursion?
Also, let the remainder function be defined as
remainder :: Integer -> Integer -> Integer
remainder a b = if a < b then a
else remainder (a - b) b
Rewrite remainder using fix so that it is non-recursive.
First of all the principal type of fix is actually (b -> b) -> b (remember that only b -> (b -> b) is the same as b -> b -> b).
In a strict language, such a definition would go into infinite recursion, but because Haskell is lazy, the arguments to a function are evaluated only if they are at any point needed. For example you can define factorial.
-- with recursion
factorial :: Int -> Int
factorial n = if n == 0 then 1 else n * factorial (n-1)
-- with `fix`
factorial' :: Int -> Int
factorial' = fix (\f n -> if n == 0 then 1 else n * f (n - 1))
Following the same pattern, you should be able to define remainder.