Làm thế nào để bạn nhận và sử dụng loại phụ thuộc từ một loại lớp với các phụ thuộc chức năng?

Question

Làm thế nào để bạn nhận và sử dụng loại phụ thuộc từ một loại lớp với các phụ thuộc chức năng?

Để làm rõ và đưa ra một ví dụ về nỗ lực mới nhất của tôi (hạn chế tối đa từ mã thực tế tôi đang viết):

class Identifiable a b | a -> b where -- if you know a, you know b 
    idOf :: a -> b 

instance Identifiable Int Int where 
    idOf a = a 

f :: Identifiable Int b => Int -> [b] -- Does ghc infer b from the functional dependency used in Identifiable, and the instance? 
f a = [5 :: Int] 

Nhưng GHC không suy ra b, có vẻ như, vì nó in lỗi này:

Couldn't match expected type ‘b’ with actual type ‘Int’ 
    ‘b’ is a rigid type variable bound by 
     the type signature for f :: Identifiable Int b => Int -> [b] 
     at src/main.hs:57:6 
Relevant bindings include 
    f :: Int -> [b] (bound at src/main.hs:58:1) 
In the expression: 5 :: Int 
In the expression: [5 :: Int] 
In an equation for ‘f’: f a = [5 :: Int] 

Đối với bối cảnh, đây là một ví dụ ít hạn chế tối đa:

data Graph a where 
    Graph :: (Identifiable a b) => GraphImpl b -> Graph a 

getImpl :: Identifiable a b => Graph a -> GraphImpl b 
getImpl (Graph impl) = impl 

Cách giải quyết ở đây sẽ có thêm b as type arg để đồ thị:

data Graph a b | a -> b where 
    Graph :: (Identifiable a b) => GraphImpl b -> Graph a 

Bối cảnh đầy đủ: Tôi có một Graph của đơn vị mà mỗi người đều có một id, mỗi thực thể được gán cho 1 nút. Bạn có thể tra cứu một nút theo thực thể. Tôi cũng có một Graph' bao gồm các nút (có thể được gán một thực thể), và để tra cứu một nút bạn cần cung cấp id của nút, đó là một Int. Graph sử dụng Graph' nội bộ. Tôi có một số IdMap để ánh xạ các id của các thực thể thành các id của các nút trong Graph'. Đây là Graph định nghĩa của tôi:

data Graph a where 
    Graph :: (Identifiable a b) => { 
    _idMap :: IdMap b, 
    _nextVertexId :: Int, 
    _graph :: Graph' a 
} -> Graph a 

---

trả lời: Sử dụng gia đình loại, xem Daniel Wagner's answer. Để xem toàn bộ câu chuyện, hãy xem Reid Barton's answer.

Answer 1

Nó thực sự có vẻ hơi lạ mà GHC phàn nàn về số tiền tối thiểu f mà bạn đã đăng ở trên cùng. Nhưng có vẻ như hoạt động tốt với các loại gia đình:

{-# LANGUAGE TypeFamilies #-} 
class Identifiable a where 
    type IdOf a 
    idOf :: a -> IdOf a 

instance Identifiable Int where 
    type IdOf Int = Int 
    idOf a = a 

f :: a -> [IdOf Int] 
f _ = [5 :: Int] 

Có lẽ bạn có thể điều chỉnh ý tưởng này thành ví dụ lớn hơn.

Answer 2

Trong triển khai của GHC, các phụ thuộc chức năng có thể hạn chế các giá trị của các biến kiểu mà nếu không sẽ không rõ ràng (theo ý nghĩa show . read). Chúng không thể được sử dụng để cung cấp bằng chứng rằng hai loại là bình đẳng, theo cách mà các ràng buộc bình đẳng có thể. Sự hiểu biết của tôi là các phụ thuộc chức năng trước khi bổ sung các ràng buộc đối với ngôn ngữ trung gian của GHC, và những sự ép buộc này là cần thiết để dịch các loại chương trình mà bạn mong muốn làm việc thành các chương trình Core được đánh máy tốt.

(Tình trạng này được cho là tốt nhất, vì GHC không thực sự thực thi điều kiện phụ thuộc chức năng trên toàn cầu và sẽ dễ dàng phá vỡ an toàn loại nếu các chương trình như chương trình đầu tiên của bạn được chấp nhận. Một phiên bản ngắn của điều này là logic của trình kiểm tra loại xung quanh các phụ thuộc chức năng không mạnh như bạn mong đợi, đặc biệt là kết hợp với các tính năng hệ thống kiểu mới hơn như GADT. Thay vào đó, tôi khuyên bạn nên sử dụng họ loại trong các tình huống này, như được minh họa bằng câu trả lời của Daniel Wagner.

https://ghc.haskell.org/trac/ghc/ticket/345 là một vé cũ về chủ đề tương tự, vì vậy bạn có thể thấy rằng đây là vấn đề đã biết từ lâu với phụ thuộc chức năng và sử dụng loại gia đình thay thế.

Nếu bạn muốn giữ lại phong cách, trong đó có hai đối số Identifiable loại, bạn cũng có thể thiết lập chương trình của bạn theo hình thức

type family IdOf a 
class (b ~ IdOf a) => Identifiable a b where 
    idOf :: a -> b 

type instance IdOf Int = Int 
instance Identifiable Int Int where 
    idOf a = a 

f :: Identifiable Int b => Int -> [b] 
f a = [5 :: Int]