Tôi nên triển khai Bảng Cayley trong Haskell như thế nào?

Question

Tôi quan tâm đến việc khái quát hóa một số công cụ tính toán để sử dụng một Cayley Table, có nghĩa là một bảng tra cứu dựa trên phép nhân.

tôi có thể tạo ra một thực hiện tối thiểu như sau:

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 

Tuy nhiên có nhiều vấn đề với cách tiếp cận này, bắt đầu với các loại thời gian chạy kiểm tra qua ByteString so sánh, nhưng trong đó có một thực tế rằng read không thể được thực hiện để hoạt động chính xác. Bất kỳ ý tưởng làm thế nào tôi nên làm điều này một cách chính xác?

tôi có thể tưởng tượng được tạo ra trong một gia đình newtypes CTElement1, CTElement2, vv cho Int với một typeclass CTElement cung cấp các phép nhân và xác minh tính nhất quán loại của họ, trừ khi làm IO. Lý tưởng nhất, có thể có một số mẹo để chỉ sử dụng một bản sao của con trỏ ct_cayleytable này, có thể sử dụng tham số ngầm như ?cayleytable, nhưng điều này không chơi độc đáo với nhiều bảng Cayley không tương thích và thường không đáng ghét.

Ngoài ra, tôi đã tập hợp rằng một chỉ mục vào một véc tơ có thể được xem như là một comonad. Có bất kỳ trường hợp comonad tốt đẹp cho vector hoặc bất cứ điều gì có thể giúp mịn ra loại kiểm tra loại, ngay cả khi cuối cùng làm nó trong thời gian chạy?

Answer 1

Điều bạn cần nhận ra là trình kiểm tra loại của Haskell chỉ kiểm tra các loại. Vì vậy, CaleyTable của bạn cần phải là một lớp học.

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

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

Nếu caleyTable không biết lúc biên dịch bạn phải sử dụng loại xếp hạng 2. Vì trình biên dịch cần thực thi bất biến mà CaleyTable tồn tại, khi mã của bạn sử dụng nó. Ví dụ:

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

. Nó cho phép bạn thực hiện các hoạt động nhóm trên CaleyTable. Nó hoạt động bằng cách kết hợp các số i và CaleyTable để tạo một kiểu mới nó chuyển đến đối số thứ ba của nó.