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

我感兴趣的概括一些计算工具使用Cayley Table，这意味着基于查找表的乘法运算。我应该如何在Haskell中实现Cayley表？

我可以创建一个最小的实现如下：

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。是否有任何漂亮的矢量实例或任何可能有助于平滑这种类型检查，即使最终在运行时执行它？

来源

2012-02-15 Jeff Burdges

为什么要使用ByteString？虽然Read实例不可能，除非你可以从名称和索引中派生出cayley表。 – ivanm 2012-02-15 10:15:45

没有理由，ct_name仅用于使'Eq CayleyTable'更快，因为Cayley表可能有数百万条目。一个'Int'也能正常工作。理想情况下，'Read'应该从类型系统中学习特定的Cayley表，大概'read“0”:: CTElementFoo'应该总是返回一个合理的值，或者如果索引是基于1的话，可能会使用1。 – 2012-02-15 12:20:13

你需要意识到的是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，则必须使用rank-2类型。由于编译器需要强制执行CaleyTable存在的不变量，因此当您的代码使用它时。

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

例如可以实施。它允许您在CaleyTable上执行组操作。它通过结合i和CaleyTable来创建一个它传递给它的第三个参数的新类型。

来源

2012-05-23 15:20:28 Peter

是的，我提到这个选项是“我能想象得到..”，但是..我应该阅读2级的类型，因为我从来没有像这样使用过它们。谢谢！ – 2015-05-25 11:56:35

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

回答

相关问题