Как мне реализовать Cayley Table в Haskell? - PullRequest
Новая
       32

Как мне реализовать Cayley Table в Haskell?

5 голосов
/ 15 февраля 2012

Я заинтересован в обобщении некоторых вычислительных инструментов для использования таблицы Кейли , что означает операцию умножения на основе таблицы поиска.

Я мог бы создать минимальную реализацию следующим образом: 

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 для вектора или что-то еще, что могло бы помочь сгладить такого рода проверку типов, даже если в конечном итоге делать это во время выполнения?

1 Ответ

1 голос
/ 23 мая 2012

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

...