Thuyết phục trình biên dịch rằng có một chuỗi cá thể hợp lệ

Question

Được rồi. Vấn đề ở đây khá trừu tượng. Chịu với tôi.

Tôi có một nhóm "Đơn vị", mỗi đơn vị có một số thuộc tính nhất định. Các tính chất này được định nghĩa trong lớp Seq, như thế này:

class Seq a x y where 
    break :: x -> (a, y) 
    build :: a -> y -> x 

Về mặt lý thuyết, loại a là loại quan trọng, x là bối cảnh sử dụng để tạo ra một a, và y là bối cảnh sử dụng để tạo ra bất kỳ thêm Seq trường hợp. break ngắt Seq xuống, build cho phép bạn tạo lại.

Trên cá nhân Seq trường hợp, tính năng này hoạt động tốt. Tuy nhiên, tôi cũng có một nhà xây dựng dữ liệu mà trông như thế này:

data a :/: b = a :/: b deriving (Eq, Ord) 
infixr :/: 

Mục tiêu của toàn bộ hoạt động này là để có thể soạn Seq trường.

Ví dụ, nếu tôi có a, b và c tất cả các trường của Seq mà a 'bối cảnh của nguồn cấp dữ liệu vào b và b' s nguồn cấp dữ liệu vào c, sau đó tôi tự động nên có một trường hợp Seq cho a :/: b :/: c. Lớp để thiết lập điều này khá đơn giản thông qua kiểu dữ liệu đệ quy:

instance (Seq a x y, Seq b y z) => Seq (a :/: b) x z where 
    break x = let 
     (a, y) = break x :: (a, y) 
     (b, z) = break y :: (b, z) 
     in (a :/: b, z) 

    build (a :/: b) z = let 
     y = build b z :: y 
     x = build a y :: x 
     in x 

Vấn đề là tôi không thể sử dụng nó. Nếu tôi xác định sau ba Seq trường hợp:

data Foo 
instance Seq Foo Integer Bool 

data Bar 
instance Seq Bar Bool Bar 

data Baz 
instance Seq Baz Bar() 

(chi tiết thực hiện redacted, xem here để biết thêm)

và một cái giếng, đánh máy break chức năng:

myBreak :: Integer -> (Foo :/: Bar :/: Baz) 
myBreak = fst . break' where 
    break' = break :: Integer -> (Foo :/: Bar :/: Baz,()) 

sau đó tôi không thể thậm chí biên dịch:

No instances for (Seq Foo Integer y, Seq Bar y y1, Seq Baz y1()) 
    arising from a use of `break' 
Possible fix: 
    add instance declarations for 
    (Seq Foo Integer y, Seq Bar y y1, Seq Baz y1()) 
In the expression: break :: Integer -> (Foo :/: (Bar :/: Baz),()) 
In an equation for break': 
    break' = break :: Integer -> (Foo :/: (Bar :/: Baz),()) 
In an equation for `myBreak': 
    myBreak 
     = fst . break' 
     where 
      break' = break :: Integer -> (Foo :/: (Bar :/: Baz),()) 

Nó nhìn tôi như myBreak không thể chắc chắn rằng có một "chuỗi làm việc" của các ngữ cảnh từ Foo → Bar → Baz. Làm thế nào tôi có thể thuyết phục trình biên dịch rằng điều này được đánh máy tốt?

Đây là một trong những chuyến du ngoạn đầu tiên của tôi vào lập trình loại, vì vậy tôi chắc chắn sẽ phá vỡ một số quy tắc được thiết lập tốt. Tôi khá tò mò về những gì tôi đang làm sai ở đây, nhưng tôi cũng mở để gợi ý về cách đạt được mục tiêu của mình tốt hơn.

Answer 1

Có thể bạn sẽ cần một hoặc hai phần mở rộng ngôn ngữ khác để thực hiện công việc này. Các vấn đề chung là các lớp học kiểu đa thông số cần để mã hóa các giả định thế giới mở như vậy, giả sử một người nào đó đến cùng và thêm

instance Seq Bar Integer Float 

instance Seq Baz Float() 

trình biên dịch sẽ không có cách nào để biết mà tập hợp các trường hợp sử dụng. Điều này có khả năng có thể gây ra hành vi không xác định.Nếu trình biên dịch chỉ "tìm ra" rằng không có trường hợp nào khác có sẵn, do đó bạn phải có nghĩa là những điều này thì bạn sẽ ở trong tình huống khó xử khi có mã có thể phá vỡ vì ai đó đã thêm một cá thể.

Giải pháp là sử dụng một số loại hàm mức loại. Vì vậy, nếu a là loại quan trọng, thì có lẽ chỉ có một sự kết hợp của x và y đi kèm với số a. Một cách để làm điều này là với functional dependencies.

class Seq a x y | a -> x, a -> y where 
    break :: x -> (a, y) 
    build :: a -> y -> x 

phụ thuộc chức năng là khá chung chung, và có thể được sử dụng hai mã hóa song ánh chức năng loại

class Seq a x y | a -> x, a -> y, x y -> a where 
    break :: x -> (a, y) 
    build :: a -> y -> x 

Nó phụ thuộc vào những gì chính xác ngữ nghĩa bạn muốn là. Ngoài ra, bạn có thể sử dụng phương pháp "từ đồng nghĩa loại liên kết" thanh lịch hơn một chút bằng cách sử dụng phần mở rộng type families.

class Seq a where 
    type X a 
    type Y a 
    break :: X a -> (a, Y a) 
    build :: a -> Y a -> X a 

instance Seq Bar where 
    type X Bar = Bool 
    type Y Bar = Bar 

Phiên bản này hiện được coi là thành ngữ nhất, và có một số lợi thế so với phiên bản phụ thuộc chức năng (mặc dù, bạn không thể mã hóa đánh dấu theo cách này). Để hoàn thành, điều này tương đương với

type family X a 
type instance X Bar = Bool 

type family Y a 
type instance Y Bar = Bar 

class Seq a where 
    break :: X a -> (a, Y a) 
    build :: a -> Y a -> X a 

instance Seq Bar 

Để chỉnh sửa: Cơ chế giải quyết ràng buộc Haskell với nhiều loại kiểu tham số là một ngôn ngữ logic giống như prolog. Càng nhiều càng tốt, bạn nên sử dụng các hàm thay vì quan hệ khi lập trình cấp loại. Ba lý do:

1. Bạn có thể nhận được từ một chức năng để một hạn chế nhưng không phải ngược lại
2. Haskell không Prolog. Hầu hết các lập trình viên của Haskell đều tìm thấy các hàm dễ dàng hơn để giải thích. Nếu bạn không biết Prolog (hoặc một ngôn ngữ logic khác), nó quan trọng hơn để gắn vào các hàm vì sự khác biệt giữa lập trình hàm và quan hệ gần như lớn như sự khác biệt giữa lập trình chức năng và bắt buộc.
3. Mặc dù điểm tương đồng, giải pháp hạn chế của Haskell là KHÔNG Prolog (trực giác tất cả các mệnh đề có một vết cắt ngay lập tức sau đầu, đừng lo lắng nếu bạn không biết điều này có nghĩa là gì). Lập trình kiểu quan hệ khó hơn nhiều so với việc viết mã bằng một ngôn ngữ có khả năng quay ngược hoàn toàn.

Đề xuất của tôi là biết cả hai chức năng phụ thuộc và chức năng type. Các hàm kiểu phù hợp tốt hơn một chút với phần còn lại của ngôn ngữ, nhưng đôi khi phụ thuộc chức năng là công cụ tốt nhất cho công việc.