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 来说是可能的，但似乎需要很长时间。我想知道将算术运算作为参数传递给 isIrrreducible 是否会更容易？

或者，这似乎可能是 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 解决方案慢，因为每个操作都通过类字典传递有限域的大小。

Answer 2

这在一定程度上取决于 Poly.T 的样子，但是你能编写一个类型的函数（例如）

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

吗？如果是这样，那么使用 Z 类型可能是有意义的，当其模数不匹配时，其操作会在运行时失败：

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"

然后您可以在普通的旧 Haskell 中编写类似的内容：

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

当然，这是一个有点不太类型安全。但从参数化来看，fmap (Z m) 显然不会引入任何不匹配的模数。