Haskell中的Prime有限域（Z/pZ），帶有運算符重載

Question

我現在有一些代碼創建了n階的素數域，並具有計算加法，乘法和它們逆的所有必要函數。它工作正常，但我真的希望能夠重載+， - ，*，/和Integral和Num中綴函數，但我不知道如何執行此操作。以下是我當前的代碼：

import Data.Maybe 

data FiniteField = FiniteField {add::(FieldElement -> FieldElement -> FieldElement), 
       addinv::(FieldElement -> FieldElement), 
       mul::(FieldElement -> FieldElement -> FieldElement), 
       mulinv::(FieldElement -> FieldElement), 
       new::(Integer -> FieldElement) 
       } 

newtype FieldElement = FieldElement Integer deriving (Eq, Show, Read) 

toInt :: FieldElement -> Integer 
toInt (FieldElement x) = x 

gcdExt :: Integer -> Integer -> (Integer, Integer, Integer) 
gcdExt a 0 = (1, 0, a) 
gcdExt a b = (t, s - q * t, g) 
    where (q, r) = quotRem a b 
      (s, t, g) = gcdExt b r 

modMulInv :: Integer -> Integer -> Integer 
modMulInv a n = i 
    where (i, _, _) = gcdExt a n 

isPrimeLoop :: Integer -> Integer -> Bool 
isPrimeLoop n i 
    | i == n = True 
    | i == 2 = (mod n i /= 0) && isPrimeLoop n (i+1) 
    | otherwise = (mod n i /= 0) && isPrimeLoop n (i+2) 

isPrime :: Integer -> Bool 
isPrime n = isPrimeLoop n 2 

newFiniteField :: Integer -> Maybe FiniteField 
newFiniteField n 
    | not (isPrime n) = Nothing 
    | otherwise = Just (FiniteField add addinv mul mulinv new) 
    where 
     add = (\x y -> FieldElement (mod (toInt x + toInt y) n)) 
     addinv = (\x -> FieldElement (mod (n - toInt x) n)) 
     mul = (\x y -> FieldElement (mod (toInt x * toInt y) n)) 
     mulinv = (\x -> FieldElement (mod (modMulInv (toInt x) n) n)) 
     new = (\x -> FieldElement x) 

Answer 1

你必須解決的主要問題是，你不應該被允許添加/乘以/ etc。不同訂單下的FiniteField的值。從類型系統的角度來看，解決方案非常簡單：爲不同的訂單賦予不同類型的值。

newtype FieldElem (n :: Nat) = FieldElem Integer 

Nat是一種（從GHC.TypeLits模塊）的居民是類型級數字文字像1，2，3等

所以，現在，你有不同的類型：

FieldElem 7  -- the type of an element of a finite field of order 7 
FieldElem 11 -- the type of an element of a finite field of order 11 

因此，如果您嘗試添加兩個不同類型的值，則會出現編譯錯誤。

> (x :: FieldElem 7) + (y :: FieldElem 11) 
Error! You can only use + on two things of the same type! 
> (x :: FieldElem 7) + (y :: FieldElem 7) 
-- result: something of type FieldElem 7 

現在，您可以實現Num實例：

這裏

instance Num (FieldElem n) where 
    (+) = ... 
    (*) = ... 

一個問題是，(+)需要知道的順序是什麼，唯一的信息是在FieldElem類型。去解決這個問題，我們需要n是KnownNat類型類（也GHC.TypeLits）的實例，它可以讓我們得到它的整數值在運行時的值：

natVal :: KnownNat n => Proxy n -> Integer 

所以，

> natVal (Proxy :: Proxy 10) 
10 
> natVal (Proxy :: Proxy 19) 
19 

所以我們的最終設計方案：（要求ScopedTypeVariables讓我們用n類型變量）

instance KnownNat n => Num (FieldElem n) where 
    FieldElem x + FieldElem y = FieldElem (mod (x + y) n) 
    where 
     n = natVal (Proxy :: Proxy n) 

等！

您可以使用智能構造函數Integer小號帶入FieldElem：

mkFieldElem :: forall n. KnownNat n => Integer -> Maybe (FieldElem n) 
mkFieldElem x | isPrime n = Just (FieldElem (mod x n)) 
       | otherwise = Nothing 
    where 
    n = natVal (Proxy :: Proxy n) 

的好處是，你能使用Haskell的類型推斷來指定要的順序：

> mkFieldElem 10 :: Maybe (FieldElem 23) 
Just (FieldElem 10)  -- :: Maybe (FieldElem 23) 

而不是手動將其作爲參數傳遞！ :)

通過使用智能構造函數（並隱藏實際的構造函數），您可以確保用戶永遠不會有任何類型的值FieldElem 8，因此您不必擔心添加錯誤訂單的字段一起。

請注意，不幸的是，fromInteger :: KnownNat n => Integer -> FieldElem n必然是部分。它必須拒絕不好的訂單。但是，基數爲的實例數量很多，部分實現fromInteger無論如何：但是，fromInteger在Num是不是個好主意，反正，和Num是一個壞的類型類，所以它的Num的錯:)

---

編輯有做的潛在方法fromInteger不偏/總：我們可以創建一個Prime類型類和只有當所Nat參數是素數：

class KnownNat n => Prime (n :: Nat) 

然後，你可以做：

mkFieldElem :: Prime n => Integer -> FieldElem n 
mkFieldElem x = FieldElem (mod x n) 
    where 
    n = natVal (Proxy :: Proxy n) 

而現在，如果你有：

instance Prime n => Num (FieldElem n) where 
    ... 
    fromInteger = mkFieldElem 

fromInteger將是一個總的功能，因爲只有實例將是素數階領域！

但是，爲了達到此目的，您需要以GHC可以理解的方式獲取Prime的實例。理論上，這可以使用GHC類型的檢查器擴展來完成---您可以編寫自己的類型檢查器擴展，以便n在編譯時處於質數的情況下被賦予Prime實例。然而，這並沒有這樣做還...你可以做下一個最好的事情是黃金岬提供運行時間證明：

witPrime :: forall n.KnownNat n => Proxy n -> Maybe (Dict (Prime n)) 
witPrime p | isPrime (natVal p) = Just (unsafeCoerce (Dict :: Dict (KnownNat n)) 
      | otherwise   = Nothing 

這是使用Dict從constraints庫，這是一種方式在運行時生成typeclass實例。如果您在類型爲Dict c的Dict構造函數上進行了模式匹配，則該案例語句中的實例c爲「範圍內」。

在我們的話，那麼，我們可以這樣做：

case witPrime (Proxy :: Proxy 11) of 
    Just Dict -> ... -- in this branch, `Prime 11` is an instance we can use 
    Nothing -> ... -- here, it isn't 

或者，我們可以在ghci中運行它：

> let x = mkFieldElem 6 :: FieldElem 11 
Error: No instance for (Prime 11) 
> case witPrime (Proxy :: Proxy 11) of 
    Just Dict -> let x = mkFieldElem 6 :: FieldElem 11 -- okay, because of Dict constructor match 
       in print x 
FieldElem 6 -- :: FieldElem 11 

Answer 2

您無法高效地在本設計中使用Num。類型類的重要之處在於派發是通過類型來完成的，而不是通過值來完成的。的Num爲FieldElement的實例也不會知道它是屬於什麼FiniteField到，所以其操作不能依賴於你的操作哪一個領域的任何方式。

有幾個方向，你可以拿這一點，將與Num一起工作。

第一個使FieldElement表達式類型與其Num實例構建表達式樹，然後可以在特定的FiniteField內對其進行求值。這具有使用非常簡單的技術的優點。當計算變得複雜時，它具有真的對內存和性能不利的缺點。

第二種是遵循Data.Fixed這樣的模式。您可以將FiniteField更改爲類，並在代表各種特定字段的空白類型上實現它，例如名稱爲F17。然後你用參數FieldElement用一個類型參數來標記它們屬於哪個FiniteField。最後，對於FiniteElement，Num的實例要求其參數具有FiniteField實例，該實例在其實現中使用。這種方法的優點是非常適合。缺點是需要一個樣板FiniteField實例您要在其中工作的每個領域。

第三個選項是非常類似於上面，但與某種類型級天然的替代定製F17相似的數據類型。 （無論是手動，還是從-XDataKinds）。然後，您可以根據類型級自然實現Num實例。這樣做的好處是可以擺脫先前方法中的所有樣板實例。缺點是它不要求類型級別的參數是一個素數，並且如果它不是素數，那麼幾個計算就是錯誤的。