On Tue, Dec 20, 2011 at 9:47 PM, Gregory Crosswhite <gcrosswhite@gmail.com> wrote:

On Dec 20, 2011, at 8:40 PM, Jesse Schalken wrote:

If you think a value might not reduce, return an error in an error monad.

Okay, I'm completely convinced! Now all that we have to do is to solve the halting problem to make your solution work... :-)

Why do you have to solve the halting problem?

Consider integer division by 0.

intDiv x y = if y > x then 0 else 1 + (intDiv (x - y) y)

This is correct, but does not reduce with y = 0. The Prelude version returns bottom in this case. Here is a version that returns an error in an Either String.

intDiv :: (Ord a, Num a) => a -> a -> Either String a

intDiv _ 0 = Left "Division by 0!"

intDiv x y = if y > x then Right 0 else intDiv (x - y) y >>= (Right . (1 +))

This is all I was talking about.

Cheers,
Greg