我试图通过在有限（Galois）场上编写一小组函数来学习一些Haskell。几年前我为计算机代数系统GNU Maxima（see here）编写了类似库的第一个版本，我想我会尝试用Haskell做同样的事情。
但是，我对自己的数据类型感到困惑。对于有限域，您需要一个基本素数q（该域的特征），以及一个多项式p（x），它是不可约的模q。如果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
这是有效的，但是不够优雅，而且我肯定非常“非Haskell-ish”。部分问题是我不知道如何将伽罗瓦域的定义（或类型）与其元素分离。
我需要做的是为一个字段提供一般类型，并在其上定义它的元素。毕竟，我可能想要对一个独立于其元素的字段做的事情，例如生成普通基础，找到原始元素，生成基元元素的对数表，生成随机元素等。
所以我想我的问题是：如何定义泛型字段的泛型类型，以便对其元素的操作尽可能自然？
我已经阅读了很多关于定义数据类型，类等的页面，我毫不怀疑其中一个包含了我的问题的解决方案。但是我读的越多，我就越困惑。我想要的只是让某些人轻轻地指出我，但是我正确地指向正确的方向。谢谢！
我不认为你的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
我之所以提到“向量”只是导致问题，你在这里向你开放的各种方法与你用向量算法的方法相同，例如只能添加相同尺寸的矢量。
将characteristic和power提升到现代Haskell（GHC> = 7.8）的类型系统中是很容易的，也就是说，
{-# LANGUAGE TypeOperators, DataKinds #-}
{-# LANGUAGE FlexibleContexts, TypeFamilies, UndecidableInstances #-}
{-# LANGUAGE StandaloneDeriving #-}
并表示多项式的系数来自finite group，其大小是特征：
import GHC.TypeLits
import Data.Modular
data GF χ -- characteristic
n -- power
= GF { irreducible :: [ℤ/χ]
, poly :: [ℤ/χ]
}
这已经让你免费获得多项式的任何加法都将模χ。
你可以furthermore express总是有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作为一种依赖类型语言使用的界限。也许只有一次总是被使用的不可约多项式，才能选择每个特征和幂？