Haskell中的多项式因式分解

Question

在hammar的帮助下,我制作了一个模块Haskell位编译

$(zModP 5)

至

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

我现在面临一个问题,我不认为我可以这样解决.

关于多项式的一个显着事实是它们在有理数中是不可约的,如果它们是不可约的模数p.我已经有一种方法,蛮力试图在给定(有限)场上对多项式进行分解.

我想尝试为多个字段运行此函数.这就是我想要的东西:

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

基本上我想尝试运行我的因子算法来进行大量的"除法"定义.

我认为这可能与TH有关,但似乎需要永远.我想知道将参数算术作为参数传递给我会更容易isIrreducible吗？

或者看起来这可能是Newtype模块可以帮助的东西,但我想不出如果没有以一种同样难的方式使用TH它会如何工作......

任何人都有任何想法如何最好地完成这个？

Answer 1

您可以使用类型级数值在有限字段中进行计算，例如使用以下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]

这种方法的优点是不需要为每个数字类型创建新的模板 haskell 实例。缺点是它可能比模板 haskell 解决方案慢，因为每个操作都通过类字典传递有限域的大小。