[NumericPrelude] Progress toward UFD implementation

[Henning Thielemann]

On Tue, 29 Jun 2010, Lewis-Sandy, Darrell wrote:

> I thought I should take a moment and update you on my progress toward implementing the proposed new classes for the numeric prelude.   The three classes which I proposed to disambiguate the PID class are those below:
>
> {- from Algebra.UniqueFactorizationDomain.hs -}
> class (Units.C a, ZeroTestable.C a, Integral.C a) => C a where
>    factors 	:: a -> [a]  		-- factor a value into its unique factorization
>    isReducible 	:: a -> Bool
>    gcdCofacts 	:: [a] -> (a,[a])
>    gcd 		:: [a] -> a
>    cofacts 	:: [a] -> [a]
>    lcm         	:: [a] -> a
>
> {- from PrincipalIdealDomain.hs -}
> class (UFD.C a, Units.C a, ZeroTestable.C a) => C a where
>    basis 		:: [a] -> a  		-- the basis of an ideal

Is the basis always a single element?


> {- from Algebra.EuclideanDomain.hs -}
> class (Units.C a, PID.C a, ZeroTestable.C a) => C a where
>    valuation      :: a -> Integer 		-- a Euclid valuation
>    extendedEuclid :: a -> a -> (a,(a,a))
>    euclid         :: a -> a -> a
>
> Have been implemented, and the instancing for a large number of numeric 
> types (atomic types, Complex, Gaussian integers, Complex numbers) have 
> been completed.  I have begun work on implementing the instances for 
> polynomials (over integer types), and have just finished debugging the 
> Hensel lifting routine.

Great! Would you provide automated tests for the non-trivial algorithms?

>  Unlike the beautiful constructive proofs, the code is lacking in 
> elegance (due largely to my hacks for modular arithmetic).

Sure, an elegant implementation would be nicer.

> I thought that this could be improved by implementing Zp as a data type 
> with appropriate class instances.  However, it seems like there is a 
> conservation of difficulty principle here -- all the different 
> approaches which I have investigated to date (up to and including 
> dependent types) appear to have drawbacks.  I noticed that you had 
> implemented both residue classes and GF(2^32-5) and was hoping that you 
> might have some thoughts on this subject.

Yes, there is no perfect solution, thus I decided to implement the 
basic functionality without fitting into any numeric type class as in
   http://hackage.haskell.org/packages/archive/numeric-prelude/0.1.3.4/doc/html/Number-ResidueClass.html
  and then I provide different interfaces to those functions in modules in 
a sub-directory. Maybe I should split also modules like Polynomial this 
way, since the basic polynomial operations are also needed somewhere else, 
without the need to refer to polynomials explicitly.