thừa số Đa thức trong Haskell

Question

Với hammar's help Tôi đã thực hiện một mẫu Haskell chút mà biên dịch

$(zModP 5) 

để

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

bây giờ tôi đang phải đối mặt với một vấn đề mà tôi không nghĩ rằng tôi có thể giải quyết việc này đường.

Một thực tế đáng chú ý về đa thức là chúng vô dụng trong các lý do nếu chúng không thể sửa đổi được một số số nguyên tố p. Tôi đã có một phương pháp mà brute-force cố gắng để nhân tố đa thức trên một trường (hữu hạn) đã cho.

Tôi muốn thử chạy chức năng này cho nhiều trường. Dưới đây là những gì tôi muốn:

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

Về cơ bản tôi muốn thử chạy thuật toán bao thanh toán cho một số lượng lớn các định nghĩa "chia".

Tôi nghĩ rằng điều này có thể làm với TH, nhưng có vẻ như nó sẽ mất mãi mãi. Tôi tự hỏi nếu nó sẽ được dễ dàng hơn để chỉ cần vượt qua các hoạt động số học của tôi trong như một tham số để isIrreducible?

Ngoài ra nó có vẻ như điều này có thể là một cái gì module Newtype có thể giúp với, nhưng tôi không thể nghĩ ra nó như thế nào sẽ làm việc mà không sử dụng TH theo một cách mà sẽ chỉ là khó khăn ...

Bất cứ ai có bất kỳ suy nghĩ về cách tốt nhất để thực hiện điều này?

Answer 1

Bạn có thể làm phép tính trong trường vô hạn sử dụng numerics loại cấp, ví dụ với gói 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] 

Cách tiếp cận này có lợi thế là không cần một ví dụ mẫu Haskell mới đối với từng loại số. Điểm bất lợi là nó có thể chậm hơn so với giải pháp haskell của mẫu, vì mỗi thao tác truyền kích thước của trường hữu hạn xung quanh thông qua một từ điển lớp.

Answer 2

Nó phụ thuộc một chút gì Poly.T trông như thế nào, nhưng bạn có thể viết một chức năng của loại (ví dụ)

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

? Nếu vậy, nó có thể làm cho tinh thần để có một loại Z mà hoạt động thất bại trong thời gian chạy khi mô đun của họ không phù hợp:

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" 

Sau đó, bạn có thể viết một cái gì đó như thế này trong đồng bằng cũ Haskell:

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

Tất nhiên, đây là một loại ít an toàn hơn. Nhưng rõ ràng từ tham số rằng fmap (Z m) sẽ không giới thiệu bất kỳ mô-đun không khớp nào.