A sample revised prelude for numeric classes
Fergus Henderson
fjh@cs.mu.oz.au
Mon, 12 Feb 2001 14:35:55 +1100
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.