4

我试图通过编写一小组用于计算有限（伽罗瓦）域的函数来学习一点 Haskell。几年前，我为计算机代数系统 GNU Maxima（参见此处）编写了一个类似库的第一个版本，我想我会尝试用 Haskell 做同样的事情。

但是，我对数据类型感到困惑。对于有限域，您需要一个基素数 q（该域的特征）和一个不可约模 q 的多项式 p(x)。如果 p(x) 的次数为 n，则该域的阶数为 q^n，并且其元素都是次数为 n-1 或更小的多项式（模 q）。

我们可以将多项式表示为其系数的列表，因此该字段的元素只是 Z_q 和长度为 n 的元素的列表（或向量，如果您愿意）。加法是按分量模 q 完成的，乘法是模 p(x) 完成的。

我想如果我能得到数据类型和加法，剩下的就很简单了。我的第一次尝试是这样的：

import Data.List

data GF = GF {characteristic::Int
             ,power::Int
             ,poly::[Int]
             ,irreducible::[Int]
             } deriving(Eq, Show)

幂元素是不必要的 - 毕竟它只是比不可约多项式的长度小一 - 但拥有它而不是必须计算它很方便。

然后我有我的附加功能：

addGF :: GF -> GF -> GF
addGF x y = GF q n zp p
  where
    q = characteristic x
    n = power x
    zp = zipWith (\i j -> rem (i+j) q) xp yp
      where
        xp = poly x
        yp = poly y
    p = irreducible x

这行得通，但不优雅，我敢肯定非常“非哈斯克尔式”。部分问题是我不知道如何将 Galois 字段的定义（或类型）与其元素分离。

我需要做的是为一个字段提供一个通用类型，并在此之上定义它的元素。毕竟，我可能想要对一个独立于其元素的字段做一些事情，例如生成标准基、查找原始元素、为原始元素生成对数表、生成随机元素等。

所以我想我的问题是：如何定义伽罗瓦域的泛型类型，使其元素的操作尽可能自然？

我已经阅读了许多关于定义数据类型、类等的页面，毫无疑问，其中之一包含了我的问题的解决方案。但我读得越多，我就越困惑。我想要的只是有人轻轻但坚定地指出我正确的方向。谢谢！

4

2 回答 2

2

characteristic在现代 Haskell (GHC>=7.8) 中提升并进入类型系统很容易power，也就是说，

{-# LANGUAGE TypeOperators, DataKinds #-}
{-# LANGUAGE FlexibleContexts, TypeFamilies, UndecidableInstances #-}
{-# LANGUAGE StandaloneDeriving #-}

并表示多项式的系数来自以大小为特征的有限群：

import GHC.TypeLits
import Data.Modular

data GF χ -- characteristic
        n -- power
   = GF { irreducible :: [ℤ/χ]
        , poly :: [ℤ/χ]
        }

这已经免费为您提供多项式上的任何加法都是模数χ。

您还可以表示总有n + 1系数：

import qualified Data.Vector.Fixed as Fix
import qualified Data.Vector.Fixed.Boxed as Fix

data GF χ n
   = GF { irreducible :: Fix.Vec (n+1) (ℤ/χ)
        , poly :: Fix.Vec (n+1) (ℤ/χ)
        }
deriving instance (KnownNat χ, Fix.Arity (n+1)) => Show (GF χ n)

addGF :: (KnownNat χ, Fix.Arity (n+1))
           => GF χ n -> GF χ n -> GF χ n
addGF (GF irr xp) (GF irr' yp)
 | irr==irr'  = GF irr $ Fix.zipWith (+) xp yp
 | otherwise  = error "Cannot add elements of finite fields with different irreducible polynomials!"

main = print (GF irr (Fix.fromList [0,0,1]) `addGF` GF irr (Fix.fromList [0,1,1])
               :: GF 2 2)
 where irr = Fix.fromList [1,1,1]

结果：

GF {irreducible = fromList [1,1,1], poly = fromList [0,1,0]}

我们必须运行时检查不可约多项式仍然很丑陋。虽然原则上也可以将其提升到类型级别，但我不确定这是否真的会很好。我们已经在这里突破了 Haskell 可以用作依赖类型语言的界限。也许只为每个特征和功率选择一次始终使用的不可约多项式就足够了？

于 2018-01-02T17:10:39.267 回答
2

我不认为你的GF类型丑陋或不正确。我看到的主要问题是addGF不强制元素可以实际添加。相反，你可以这样做：

addGF :: GF -> GF -> Maybe GF
addGF x y -- the pipes below are called "guards", a multi-way `if` syntax
  | q == characteristic y && n == power y && p == irreducible y = Just $ GF q n zp p
  | otherwise = Nothing
  where
    q = characteristic x
    n = power x
    zp = zipWith (\i j -> rem (i+j) q) xp yp
      where
        xp = poly x
        yp = poly y
    p = irreducible x

将字段的概念与其元素分开可能更符合人体工程学和有用（但不是根本不同的解决方案），如下所示：

-- these names are probably not appropriate
data Field  
  = Field { characteristic::Int
          , power::Int
          , irreducible::[Int]
          } deriving(Eq, Show)

-- formerly `GF`:
data FieldElement
  = FieldElement 
          { field::Field
          , poly::[Int]
          } deriving(Eq, Show)

然后在上面的守卫中，你只需要做例如

...
| field x == field y = Just $ ...

RecordWildCards当您希望使用记录名称时，它也是删除样板的一个很好的扩展。

如果您知道您将使用编译时已知参数的特定字段，那么您可以允许类型检查器addGF为您强制执行不变量。一种方法是这样的：

-- see `Data.Proxy` for info about this idiom
class SomeField f where
   characteristic :: proxy f -> Int
   power :: proxy f -> Int
   irreducible :: proxy f -> [Int]

-- A field element is just the polynomial, tagged with its field using the `f` type parameter
-- you may want to not expose the internals of `GF` but instead expose a 
-- makeGF function which enforces whatever invariants should hold between the parameters
-- of a field and the polynomial of its element.
newtype GF f = GF { poly :: [Int] }

-- `addGF` is no longer partial; the type system enforces that both arguments are elements of the same field
addGF :: (SomeField f)=> GF f -> GF f -> GF f
addGF x@(GF xp) (GF yp) = GF $ zipWith (\i j -> rem (i+j) q) xp yp
  where q = characteristic x

我提到“向量”只是导致问题的原因，您在这里向您开放的各种方法与您使用向量算术的方法相同，例如只能添加相同维度的向量。

于 2018-01-02T15:40:34.523 回答