[NumericPrelude] Progress toward UFD implementation

Henning Thielemann lemming at henning-thielemann.de
Wed Jun 30 07:08:32 EDT 2010

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
  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.

More information about the Numeric-Prelude mailing list