因式分解在Haskell

Question

隨着hammar's help我做了一個模板哈斯克爾位，它編譯

$(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解決方案慢，因爲每個操作都通過類字典傳遞有限域的大小。

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" 

然後，你可以寫這樣的事情在普通的舊哈斯克爾：

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

當然，這是少了一些類型安全。但從參數清晰可見，fmap (Z m)不會引入任何不匹配的模態。