haskell - 在 GF4 上定义代数

Question

如何在 Haskell 中定义有限场幂 4 (GF4) 上的代数运算？

我有数字：0、1、2、3

运算符可能如下所示：

(+) x y = (x + y) `mod` 4
(*) 0 y = 0
(*) 1 y = y
(*) x 0 = 0
(*) x 1 = x
(*) 2 2 = 3
(*) 3 3 = 2
(*) 2 3 = 1
(*) 3 2 = 1

注意：(*) 不是多模 4！

我想得到这样的东西：

3 * 2 :: GF4 == 1 :: GF4 

我写：

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

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

但是没有成功！如何按类型类或类型编写此运算符的实现？

标签： haskell

Answer 1

像这样：

data GF4 = GF4_0 | GF4_1 | GF4_2 | GF4_3
    deriving (Bounded, Enum, Eq, {- Ord, maybe? -} Read, Show)

instance Num GF4 where
    -- A small trick to avoid having to write all the cases by hand:
    -- reuse the `Num Int` instance and use the `Enum GF4` instance to
    -- convert back and forth.

    -- BUT note that, though this was the original question's spec for
    -- (+), this is not how addition in GF4 is usually defined. Thanks
    -- to chi for pointing it out. Presumably the definition for x - y
    -- below also needs to be updated; perhaps defining negate instead
    -- would involve less repetition.
    x + y = toEnum ((fromEnum x + fromEnum y) `mod` 4)

    GF4_0 * y = 0
    GF4_1 * y = y
    GF4_2 * GF4_2 = GF4_3
    -- etc.

    -- and a couple other bookkeeping functions; see :info Num or the haddocks
    x - y = toEnum ((fromEnum x - fromEnum y) `mod` 4)
    fromInteger n = toEnum (fromInteger (n `mod` 4))
    abs = id
    signum = toEnum . signum . fromEnum

现在你可以在 ghci 中尝试一下：

> (3 * 2 :: GF4) == (1 :: GF4)
True

使Num实例不那么乏味的另一个选择是将其明确表示为具有 mod-2 系数的多项式。我将使用我之前使用过几次的愚蠢技巧，将Bool其视为 mod-2 数字（False代表 0 和True代表 1）：

instance Num Bool where
    (+) = (/=)
    (*) = (&&)
    negate = not
    abs = id
    signum = id
    fromInteger = odd

（对 Haskell 专家的补充：如果孤立实例让您感到不安，请随意更明确地定义data Bit = O | I和写出该Num实例。）

现在我们定义GF4有两个字段（编程意义上的“字段”，而不是数论意义上的）：

data GF4 = Bool :×+ Bool deriving (Eq, {- Ord, maybe? -} Read, Show)

the×+应该是一个视觉双关语：我们将ax + b表示为a:×+b. 现在（更正后的）Num实例看起来更加有序：

instance Num GF4 where
    (a:×+b) + (a':×+b') = (a + a'):×+(b + b')
    (a:×+b) * (a':×+b') = (a*a' + a*b' + b*a'):×+(a*a' + b*b')
    negate = id
    abs = id
    signum (a:×+b) = 0:×+(a*b)
    fromInteger n = 0:×+fromInteger n

x :: GF4
x = 1:×+0

与前面的例子不同，并不是所有的居民GF4都可以作为字面数字使用——只有常数多项式。所以我们定义了一个额外的值 ,x来访问非常数多项式。（或者您可以直接使用构造函数。）现在我们可以在 ghci 中试用您的示例；你叫什么2我叫x，你叫什么3我叫x+1。

> (x+1) * x == 1
True