如何在Haskell中正确实现GF4（4阶有限域）的自定义代数运算

问题描述 #

需要定义元素取值为0、1、2、3的4阶有限域GF4，遵循给定的自定义运算规则，最终实现3 * 2 :: GF4 == 1 :: GF4的判断结果为True。

运算规则 #

加法规则 #

直接使用模4加法：(+) x y = (x + y) mod 4

乘法规则（非普通模4乘法） #

• 零元规则：(*) 0 y = 0、(*) x 0 = 0
• 单位元规则：(*) 1 y = y、(*) x 1 = x
• 非平凡元素运算规则：
  • (*) 2 2 = 3
  • (*) 3 3 = 2
  • (*) 2 3 = 1
  • (*) 3 2 = 1

此前错误实现说明 #

最初尝试的代码结构如下，无法正常编译运行：

class GF4 x where
  (+), (*) :: x -> x -> x

instance GF4 where
  0 + 0 = 0
  ...
  2 * 3 = 1
  ...

核心错误点 #

• 类型类GF4 x要求实例必须绑定具体类型参数，裸instance GF4 where不符合Haskell实例声明语法
• 直接对0/1/2/3字面量做模式匹配时，Haskell无法推断字面量对应类型，会抛出模糊类型错误
• 自定义的(+)/(*)与Prelude默认同名运算存在作用域冲突

正确实现步骤 #

1. 定义GF4专属新类型 #

使用newtype封装整数类型，与普通整数运算做明确区分：

newtype GF4 = GF4 Int
  deriving (Eq, Show) -- 预先支持相等判断、调试输出

可选优化：编写智能构造函数，自动将输入值规束到0-3的合法取值范围：

mkGF4 :: Int -> GF4
mkGF4 n = GF4 (n `mod` 4)

2. 实现运算逻辑（兼容原生运算符写法） #

为了可以直接使用+/*运算符，直接为GF4实现标准库的Num类型类实例，所有规则按要求匹配：

instance Num GF4 where
  -- 加法：直接走模4规则
  (GF4 x) + (GF4 y) = mkGF4 (x + y)

  -- 乘法：按给定自定义规则匹配
  (GF4 0) * _ = GF4 0
  _ * (GF4 0) = GF4 0
  (GF4 1) * y = y
  x * (GF4 1) = x
  (GF4 2) * (GF4 2) = GF4 3
  (GF4 3) * (GF4 3) = GF4 2
  (GF4 2) * (GF4 3) = GF4 1
  (GF4 3) * (GF4 2) = GF4 1

  -- Num类型类要求的其余方法，按域规则实现即可
  negate (GF4 x) = GF4 ((4 - x) `mod` 4) -- 加法逆元
  abs = id -- GF4无绝对值概念，直接返回本身
  signum (GF4 0) = GF4 0
  signum _ = GF4 1 -- 非零元素符号统一为单位元
  fromInteger n = mkGF4 (fromInteger n) -- 数字字面量自动转换为GF4值

效果验证 #

在GHCi中执行以下代码即可得到符合预期的结果：

3 * 2 :: GF4
-- 输出：GF4 1

(3 * 2 :: GF4) == (1 :: GF4)
-- 输出：True

内容的提问来源于stack exchange，提问作者evgkch