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 に答える