math - 我应该如何在 Haskell 中实现凯莱表？

Question

我有兴趣推广一些计算工具以使用 Cayley Table ，表示基于查找表的乘法运算。

我可以创建一个最小的实现，如下所示:

date CayleyTable = CayleyTable {
    ct_name :: ByteString,
    ct_products :: V.Vector (V.Vector Int)
} deriving (Read, Show)

instance Eq (CayleyTable) where
 (==) a b = ct_name a == ct_name b

data CTElement = CTElement { 
    ct_cayleytable :: CayleyTable,
    ct_index   :: !Int
}

instance Eq (CTElement) where
 (==) a b = assert (ct_cayleytable a == ct_cayleytable b) $
            ct_index a == ct_index b

instance Show (CTElement) where
   show = ("CTElement" ++) . show . ctp_index

a **** b = assert (ct_cayleytable a == ct_cayleytable b) $
           ((ct_cayleytable a) ! a) ! b

然而，这种方法存在许多问题，首先是通过 ByteString 比较进行运行时类型检查，但还包括 read 无法正常工作的事实。知道我应该如何正确地做到这一点吗？

我可以想象使用 CTElement 为 Int 创建一系列新类型 CTElement1、CTElement2 等提供乘法并验证其类型一致性的类型类，执行 IO 时除外。

理想情况下，也可能存在一些技巧来仅传递此 ct_cayleytable 指针的一个副本，也许使用像 ?cayleytable 这样的隐式参数，但这并不与多个不兼容的 Cayley 表一起玩得很好，但通常会令人讨厌。

此外，我还发现向量的索引可以被视为comonad。是否有任何好的 comonad 向量实例或任何可能有助于平滑这种类型检查的东西，即使最终在运行时进行？

Answer 1

你需要意识到的是 Haskell 的类型检查器只检查类型。所以你的 CaleyTable 需要是一个类。

class CaleyGroup g where
caleyTable :: g -> CaleyTable
... -- Any operations you cannot implement soley by knowing the caley table

data CayleyTable = CayleyTable {
...
} deriving (Read, Show)

如果 caleyTable 在编译时未知，则必须使用 2 级类型。由于当您的代码使用 CaleyTable 时，编译器需要强制执行 CaleyTable 存在的不变式。

manipWithCaleyTable :: Integral i => CaleyTable -> i -> (forall g. CaleyGroup g => g -> g) -> a

例如可以实现

。它允许您对 CaleyTable 执行分组操作。它的工作原理是结合 i 和 CaleyTable 来创建一个传递给第三个参数的新类型。