Come devo implementare un tavolo Cayley in Haskell?

Question

Sono interessato a generalizzare alcuni strumenti di calcolo per utilizzare uno Cayley Table, che indica un'operazione di moltiplicazione basata sulla tabella di ricerca.

ho potuto creare un'implementazione minimale come segue:

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 

ma sono numerosi problemi con questo approccio, iniziando con il tipo di tempo di funzionamento controllando via ByteString confronti, ma compreso il fatto che read non possono essere fatti per funziona correttamente Qualche idea su come dovrei farlo correttamente?

Ho potuto immaginare la creazione di una famiglia di newtypes CTElement1, CTElement2, ecc per Int con un typeclass CTElement che fornisce la moltiplicazione e verifica il loro tipo di coerenza, tranne quando si fa IO.

Idealmente, ci potrebbe essere qualche trucco per passare intorno solo una copia di questo puntatore ct_cayleytable troppo, magari utilizzando un parametro implicito come ?cayleytable, ma questo non giocare bene con più tabelle Cayley incompatibili e ottiene generalmente antipatico.

Inoltre, ho capito che un indice in un vettore può essere visto come una comonade. C'è qualche bella istanza di comonad per il vettore o qualsiasi altra cosa che potrebbe aiutare a smussare questo tipo di controllo dei tipi, anche se alla fine lo si fa in fase di runtime?

Answer 1

La cosa che devi capire è che il controllo tipo di Haskell controlla solo i tipi. Quindi il tuo CaleyTable deve essere una classe.

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

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

Se il caleyTable non è noto in fase di compilazione, è necessario utilizzare i tipi rank-2. Poiché il compilatore deve applicare l'invariante che CaleyTable esiste, quando viene utilizzato dal codice.

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

può essere implementato per esempio. Ti consente di eseguire operazioni di gruppo su CaleyTable. Funziona combinando i e CaleyTable per rendere un nuovo tipo che passa al terzo argomento.