Как я должен использовать таблицу Cayley в 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 не может быть сделана работайте правильно. Любая идея, как я должен делать это правильно?

я мог себе представить, создавая семью ньютайпов CTElement1, CTElement2 и т.д. для Int с CTElement класса типов, что обеспечивает умножение и проверяет их тип последовательности, за исключением того, при выполнении операций ввода-вывода.

В идеале, может быть какой-то трюк для прохождения вокруг только один экземпляр этого ct_cayleytable указателя тоже, возможно, используя неявный параметр, как ?cayleytable, но это не играет хорошо с несколькими несовместимыми таблицами Кэли и получает вообще неприятны.

Кроме того, я понял, что индекс в вектор можно рассматривать как 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, когда ваш код использует его.

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

может быть реализован, например. Он позволяет выполнять групповые операции на CaleyTable. Он работает, объединяя i и CaleyTable, чтобы сделать новый тип, который он передает своему третьему аргументу.