On 11-Feb-2001, Dylan Thurston
class (Num a) => Integral a where div, mod :: a -> a -> a divMod :: a -> a -> (a,a) gcd, lcm :: a -> a -> a extendedGCD :: a -> a -> (a,a,a)
-- Minimal definition: divMod or (div and mod) -- and extendedGCD, if the provided definition does not work div a b | (d,_) <- divMod a b = d mod a b | (_,m) <- divMod a b = m divMod a b = (div a b, mod a b) gcd a b | (_,_,g) <- extendedGCD a b = g extendedGCD a b = ... -- insert Euclid's algorithm here lcm a b = (a `div` gcd a b) * b
Integral has the mathematical structure of a unique factorization domain, satisfying the laws
a * b === b * a (div a b) * b + (mod a b) === a mod (a+k*b) b === mod a b a `div` gcd a b === zero gcd a b === gcd b a gcd (a + k*b) b === gcd a b a*c + b*d === g where (c, d, g) = extendedGCD a b
TODO: quot, rem partially defined. Explain. The default definition of extendedGCD above should not be taken as canonical (unlike most default definitions); for some Integral instances, the algorithm could diverge, might not satisfy the laws above, etc.
In that case, I think it might be better to not provide it as a default, and instead to provide a function called say `euclid_extendedGCD'; someone defining an instance can then extendedGCD = euclid_extendedGCD if that is appropriate. It's so much easier to find bugs in code that you did write rather than bugs which are caused by what you *didn't* write. Of course this is not so effective if we keep the awful Haskell 98 rule that instance methods always default to bottom if not defined; but even if that rule is not changed, compilers can at least warn about that case.
class (Num a, Additive b) => Powerful a b where (^) :: a -> b -> a
I don't like the name. Plain `Pow' would be better, IMHO.
Apart from those two points, I quite like this proposal,
at least at first glance.
--
Fergus Henderson