Haskell polynomial factorization

Question

With hammar help, I created a Haskell template that compiles

$(zModP 5) 

to

 newtype Z5 = Z5 Int instance Additive.C Z5 where (Z5 x) + (Z5 y) = Z5 $ (x + y) `mod` 5 ... 

Now I have a problem, I don’t think I can solve this way.

The remarkable fact about polynomials is that they are irreducible in rational ones if they are irreducible modulo some prime p . I already have a method that brute force tries to lay polynomials over a given (final) field.

I want to try running this function for several fields. Here is what I want:

 isIrreducible :: (FiniteField.C a) => Poly.T a -> Bool isIrreducible p = ... intPolyIrreducible :: Poly.T Int -> Bool intPolyIrreducible p = isIrreducible (p :: Poly.T Z2) || isIrreducible (p :: Poly.T Z3) || isIrreducible (p :: Poly.T Z5) || ... 

Basically, I want to try running a factoring algorithm for a large number of "division" definitions.

I think it's possible to do this with TH, but it looks like it's forever. I am wondering if it is easy to pass my arithmetic operations as an isIrreducible parameter?

Alternatively, it seems like it could be something like a Newtype module, but I can't figure out how it will work without using TH in a way that would be difficult ...

Anyone have any thoughts on how best to do this?

Answer 1

You can perform calculations in finite fields using numerical values ​​of the type, for example, with the type-level package:

 {-# LANGUAGE ScopedTypeVariables #-} module Mod where import Data.TypeLevel.Num (Nat,toNum, reifyIntegral) data Z p = Z Integer instance Eq (Z p) where Z x == Z y = x == y instance Ord (Z p) where -- dummy instance instance Show (Z p) where show (Z n) = show n instance Nat p => Num (Z p) where Z x + Z y = Z $ (x + y) `mod` toNum (undefined :: p) Z x - Z y = Z $ (x - y) `mod` toNum (undefined :: p) Z x * Z y = Z $ (x * y) `mod` toNum (undefined :: p) fromInteger n = Z (n `mod` toNum (undefined :: p)) -- etc -- Compute x^2-6 (mod p) poly :: Nat p => Z p -> Z p poly x = x*x-6 -- Computes whether x^2-6==0 (mod p), for x=3 checkPoly :: Integer -> Bool checkPoly n = reifyIntegral n test where test :: forall p . Nat p => p -> Bool test _ = poly (3::Z p) == 0 test1 = map checkPoly [2,3,5] -- Result: [False,True,False] 

This approach has the advantage that a new instance of the haskell pattern is not required for each number type. The disadvantage is that it is probably slower than solving the haskell template, since each operation passes the size of the final field around through the class dictionary.

Answer 2

It depends a bit on what Poly.T looks like, but can you write a function like (for example)

 fmap :: (a -> b) -> (Poly.T a -> Poly.T b) 

? If so, it might make sense to have type Z whose operations are not executed at run time when their module does not match:

 data Z = Z Int Int instance Applicative.CZ where (Z mv) + (Z m' v') | m == m' = Z m ((v + v') `mod` m) | otherwise = error "mismatched modulus" 

Then you can write something like this in a plain old Haskell:

 intPolyIrreducible :: Poly.T Int -> Bool intPolyIrreducible p = any isIrreducible [fmap (Z m) p | m <- [2,3,5,7,11,13]] 

Of course, this is a little less safe. But due to parametrism, it is clear that fmap (Z m) will not introduce any inconsistent modules.