[NumericPrelude] Progress toward UFD implementation

Lewis-Sandy, Darrell darrelll at amgen.com
Tue Jun 29 19:15:22 EDT 2010

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

{- 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.   Unlike the beautiful constructive proofs, the code is lacking in elegance (due largely to my hacks for modular arithmetic).  

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.

More information about the Numeric-Prelude mailing list