YAP (was Re: Proposal: Remove Show and Eq superclasses of Num)

[Paterson, Ross]

Tyson Whitehead writes:
> I was also wondering about the EuclidanDomain "associate" and "unit"
> functions.  YAP requires, for all x
>
>   x = associate x * unit x  (where unit x has an multiplicative inverse)
>   associate (unit x) = unit (associate x) = 1
>
> http://hackage.haskell.org/packages/archive/yap/0.1/doc/html/Data-YAP-
> Algebra.html#t:EuclideanDomain
>
> This seem very much like generalized absolute and signum functions.

The two concepts are similar for Int and Integer, except that signum 0 = 0
while unit 0 = 1, but the meanings of abs and signum on other types
generalize in a different way.

These functions are pretty common in computer algebra systems.

> The wikipedia page on Euclidean Domains, however, doesn't mention such
> functions.  Rather it works with the concept of a "euclidian" function which
> gives a mapping onto the non-negative integers such that
>
>   euclidean (mod a b) < euclidean b  whenever  mod a b /= 0
>
> http://en.wikipedia.org/wiki/Euclidean_domain#Definition
>
> Are these two viewpoints connected?  Does a Euclidian domain's euclidian
> function somehow give rise to the "associate" and "unit" functions?

The purpose of the EuclideanDomain class is to allow us to use Euclid's
algorithm, defining

   gcd :: EuclideanDomain a => a -> a -> a

and with that

   instance EuclideanDomain a => Field (Ratio a)

The Euclidean function is the measure function into a well-ordered set
(the naturals) used in the proof that gcd terminates.  You don't actually
use it in the code.  On the other hand you do need to be able to get a
canonical associate.