factorización de polinomios en Haskell

Question

Con hammar's help he hecho un poco de Haskell plantilla que compila

$(zModP 5) 

a

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

ahora estoy frente a un problema que no creo que pueda resolver este camino.

Un hecho notable sobre los polinomios es que son irreductibles en los racionales si son módulos irreducibles algunos primeros p. Ya tengo un método que fuerza bruta intenta factorizar polinomios sobre un campo dado (finito).

Quiero intentar ejecutar esta función para múltiples campos. He aquí algo de lo que quiero:

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

Básicamente quiero probar el funcionamiento de mi algoritmo de factorización de un gran número de definiciones de "división".

Creo que esto es posible con TH, pero parece que llevaría una eternidad. Me pregunto si sería más fácil pasar mis operaciones aritméticas como un parámetro al isIrreducible?

Alternativamente Parece que esto podría ser algo que el módulo de Newtype podría ayudar, pero no puedo pensar en cómo funcionaría sin el uso de TH de una manera que sería tan duro ...

Cualquiera ¿Alguna idea de cómo lograr esto?

Answer 1

Puede hacer cálculos en campos finitos utilizando valores numéricos a nivel de tipo, por ejemplo, con el paquete type-level:

{-# 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] 

Este enfoque tiene la ventaja de no requerir una nueva instancia de plantilla Haskell para cada tipo numérico. La desventaja es que probablemente sea más lenta que la solución haskell de plantilla, ya que cada operación pasa el tamaño del campo finito a través de un diccionario de clase.

Answer 2

Depende un poco lo que Poly.T se parece, pero se puede escribir una función de tipo (por ejemplo)

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

? Si es así, podría tener sentido tener un tipo Z cuyas operaciones fallar en tiempo de ejecución cuando su módulo no coincide:

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

Entonces se puede escribir algo como esto en el viejo y simple Haskell:

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

Por supuesto, esto es un poco menos seguro. Pero está claro desde la parametricidad que fmap (Z m) no introducirá ningún módulo incompatible.