Jak powinienem wdrożyć tabelę Cayleya w Haskell?

Question

Jestem zainteresowany uogólnieniem niektórych narzędzi obliczeniowych do użycia Cayley Table, co oznacza operację mnożenia opartą na tablicy odnośników.

mogę tworzyć minimalną realizację następująco:

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 

Istnieją jednak liczne problemy z tym podejściem, począwszy od typu w czasie wykonywania kontroli przez ByteString porównań, ale w tym fakt, że read nie może zostać dokonane działa poprawnie. Masz pomysł, jak powinienem to zrobić poprawnie?

mogę sobie wyobrazić stworzenie rodziny newtypes CTElement1, CTElement2 itp dla Int z CTElement typeclass udostępniającej mnożenie i weryfikuje ich rodzaj spójności, z wyjątkiem, gdy robi IO.

Idealnie, nie mogą być pewne trick przechodząc wokół tylko jedną kopię tego ct_cayleytable wskaźnik też, być może przy użyciu niejawny parametr jak ?cayleytable, ale nie grać ładnie z wielu niekompatybilnych tabel Cayley i dostaje zazwyczaj nieprzyjemny.

Ponadto, stwierdziłem, że indeks do wektora może być postrzegany jako komonad. Czy istnieje jakaś dobra instancja komonad dla wektora lub cokolwiek, co może pomóc w wygładzeniu tego rodzaju sprawdzania typów, nawet jeśli ostatecznie robi to w czasie wykonywania?

Answer 1

Musisz sobie uświadomić, że kontroler typu Haskella sprawdza tylko typy. Zatem Twoja CaleyTable musi być klasą.

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

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

Jeśli caleyTable nie jest znana w czasie kompilacji, musisz użyć typów rangi 2. Ponieważ kompilator musi wymusić niezmiennik, że istnieje CaleyTable, kiedy twój kod go używa.

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

może być zaimplementowany na przykład. Umożliwia wykonywanie operacji grupowych na CaleyTable. Działa poprzez połączenie i i CaleyTable, aby nowy typ przejdzie do trzeciego argumentu.