How should I implement a Cayley Table in Haskell?

Question

I'm interested in generalizing some computational tools to use a Cayley Table, meaning a lookup table based multiplication operation.

I could create a minimal implementation as follows :

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

There are however numerous problems with this approach, starting with the run time type checking via ByteString comparisons, but including the fact that read cannot be made to work correctly. Any idea how I should do this correctly?

I could imagine creating a family of newtypes CTElement1, CTElement2, etc. for Int with a CTElement typeclass that provides the multiplication and verifies their type consistency, except when doing IO.

Ideally, there might be some trick for passing around only one copy of this ct_cayleytable pointer too, perhaps using an implicit parameter like ?cayleytable, but this doesn't play nicely with multiple incompatible Cayley tables and gets generally obnoxious.

Also, I've gathered that an index into a vector can be viewed as a comonad. Is there any nice comonad instance for vector or whatever that might help smooth out this sort of type checking, even if ultimately doing it at runtime?

Answer 1

You thing you need to realize is that Haskell's type checker only checks types. So your CaleyTable needs to be a class.

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

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

If the caleyTable isn't known at compile time you have to use rank-2 types. Since the complier needs to enforce the invariant that the CaleyTable exists, when your code uses it.

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

can be implemented for example. It allows you to perform group operations on the CaleyTable. It works by combining i and CaleyTable to make a new type it passes to its third argument.