2012-02-15 7 views
5

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.Jak powinienem wdrożyć tabelę Cayleya w Haskell?

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?

+0

Dlaczego warto używać ByteString? Chociaż instancja Read nie będzie możliwa, chyba że można wyprowadzić tabelę cayley tylko z nazwy i indeksu. – ivanm

+0

Nie ma powodu, ct_name istnieje tylko po to, aby szybciej utworzyć 'Eq CayleyTable', ponieważ tabela Cayley może zawierać miliony wpisów. "Int" też działa dobrze. Idealnie, 'Read' powinien nauczyć się konkretnej tabeli Cayleya z systemu typów, prawdopodobnie" czytaj "0" :: CTElementFoo "powinien zawsze zwracać rozsądną wartość, lub może używając 1 zamiast, jeśli indeksy są oparte na 1. –

Odpowiedz

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.

+0

Tak, wspomniałem tę opcję jako "Mogłem sobie wyobrazić ...", ale ... Powinienem czytać na 2 kategoriach, ponieważ nigdy ich nie używałem w ten sposób. dzięki! –