我应该如何在Haskell中实现Cayley表？

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无法正常工作的事实.知道我该如何正确地做到这一点？

我能想象创造一个家庭newtypes的CTElement1,CTElement2对等,Int有CTElement提供乘法并验证其类型的一致性,这样做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来创建一个传递给第三个参数的新类型。