8

在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 它将如何工作......

有人对如何最好地实现这一点有任何想法吗？

4

2 回答 2

3

您可以使用类型级别的数字在有限域中进行计算，例如使用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 解决方案慢，因为每个操作都通过类字典传递有限域的大小。

于 2011-10-07T21:00:08.383 回答
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)不会引入任何不匹配的模数的参数化中可以清楚地看出。

于 2011-10-07T14:43:51.920 回答