A sample revised prelude for numeric classes

[Fergus Henderson]

On 11-Feb-2001, Dylan Thurston <dpt@math.harvard.edu> wrote:
> > 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 <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.