Làm thế nào để statisfy một lớp hạn chế trong một thể hiện của một lớp đòi hỏi một constructor kiểu chứ không phải là một loại cụ thể?

Question

Tôi hiện đang ở Chapter 8 trong số Learn you a Haskell và tôi đã đến phần trên Functor kiểu chữ. Trong phần nói trên, tác giả đưa ra các ví dụ về cách các kiểu khác nhau có thể được tạo ra trong các lớp (ví dụ: Maybe, một kiểu tùy chỉnh Tree, v.v.) Xem này, tôi quyết định (để vui và thực hành) thử thực hiện một thể hiện cho loại Data.Set ; trong tất cả điều này bỏ qua Data.Set.map, tất nhiên.

Các ví dụ thực tế chính nó là khá thẳng về phía trước, và tôi đã viết nó như:

instance Functor Set.Set where 
    fmap f empty = Set.empty 
    fmap f s = Set.fromList $ map f (Set.elems s) 

Nhưng, kể từ khi tôi xảy ra để sử dụng chức năng fromList này mang lại trong một hạn chế lớp gọi cho các loại được sử dụng trong Set là Ord, như được giải thích bởi một lỗi biên dịch:

Error occurred 
ERROR line 4 - Cannot justify constraints in instance member binding 
*** Expression : fmap 
*** Type   : Functor Set => (a -> b) -> Set a -> Set b 
*** Given context : Functor Set 
*** Constraints : Ord b 

Xem: Live Example

tôi tri ed đặt một ràng buộc vào cá thể, hoặc thêm chữ ký loại vào fmap, nhưng không thành công (cả hai đều là lỗi trình biên dịch.)

Với một tình huống như thế này, làm thế nào một ràng buộc có thể được đáp ứng và thỏa mãn? Có cách nào có thể không?

Cảm ơn trước! :)

Answer 1

Thật không may, có không cách dễ dàng để thực hiện việc này với lớp tiêu chuẩn Functor. Đây là lý do tại sao Set không đi kèm với một trường hợp Functor theo mặc định: bạn không thể viết một.

Đây là vấn đề và đã có một số giải pháp được đề xuất (ví dụ: xác định Functor lớp theo cách khác), nhưng tôi không biết liệu có sự đồng thuận về cách xử lý tốt nhất điều này hay không.

Tôi tin rằng một cách tiếp cận là viết lại lớp Functor sử dụng constraint kinds để sửa lại các trường hợp ràng buộc bổ sung của lớp Functor mới có thể có. Điều này sẽ cho phép bạn chỉ định rằng Set phải chứa các loại từ lớp Ord.

Cách tiếp cận khác chỉ sử dụng các lớp đa thông số. Tôi chỉ có thể tìm thấy bài viết về việc này cho lớp Monad, nhưng làm cho Set một phần của Monad đối mặt với cùng một vấn đề khi đặt thành một phần của Functor. Nó được gọi là Restricted Monads.

Các ý chính cơ bản của việc sử dụng các lớp học đa số ở đây có vẻ là một cái gì đó như thế này:

class Functor' f a b where 
    fmap' :: (a -> b) -> f a -> f b 

instance (Ord a, Ord b) => Functor' Data.Set.Set a b where 
    fmap' = Data.Set.map 

Về cơ bản, tất cả các bạn đang làm ở đây là làm cho các loại trong các Set cũng là một phần của lớp . Điều này sau đó cho phép bạn hạn chế những gì các loại này có thể được khi bạn viết một thể hiện của lớp đó.

Phiên bản này của Functor cần hai tiện ích mở rộng: MultiParamTypeClasses và FlexibleInstances.(Bạn cần phần mở rộng đầu tiên để có thể xác định lớp và phần mở rộng thứ hai để có thể xác định một cá thể cho Set.)

Haskell : An example of a Foldable which is not a Functor (or not Traversable)? có một cuộc thảo luận tốt về điều này.

Answer 2

Điều này là không thể. Mục đích của lớp học Functor là nếu bạn có Functor f => f a, bạn có thể thay thế a bằng bất kỳ thứ gì bạn thích. Các lớp học không được phép hạn chế bạn chỉ trả lại này hoặc đó. Vì Set yêu cầu các phần tử của nó thỏa mãn các ràng buộc nhất định (và thực sự đây không phải là một chi tiết thực hiện nhưng thực sự là một thuộc tính thiết yếu của bộ), nó không đáp ứng các yêu cầu của Functor.

Có, như đã đề cập trong câu trả lời khác, cách phát triển một lớp như Functor không hạn chế bạn theo cách đó, nhưng nó thực sự là một lớp khác, vì nó mang lại cho người dùng lớp bảo đảm ít hơn (bạn không có thể sử dụng điều này với bất kỳ tham số kiểu nào bạn muốn), để đổi lấy việc áp dụng cho một phạm vi rộng hơn các loại. Đó là, sau khi tất cả, sự cân bằng cổ điển của việc xác định một tài sản của các loại: các loại hơn bạn muốn đáp ứng nó, ít hơn họ phải được buộc phải đáp ứng.

(Một ví dụ thú vị về nơi này xuất hiện là lớp MonadPlus. Đặc biệt, đối với mỗi trường hợp MonadPlus TC bạn có thể làm một ví dụ Monoid (TC a), nhưng bạn có thể không phải lúc nào đi theo con đường khác xung quanh. Do đó dụ Monoid (Maybe a) là khác nhau từ MonadPlus Maybe dụ, bởi vì trước đây có thể hạn chế a nhưng sau này thì không thể.)

Answer 3

You can do this using a CoYoneda Functor.

{-# LANGUAGE GADTs #-} 

data CYSet a where 
    CYSet :: (Ord a) => Set.Set a -> (a -> b) -> CYSet b 

liftCYSet :: (Ord a) => Set.Set a -> CYSet a 
liftCYSet s = CYSet s id 

lowerCYSet :: (Ord a) => CYSet a -> Set.Set a 
lowerCYSet (CYSet s f) = Set.fromList $ map f $ Set.elems s 

instance Functor CYSet where 
    fmap f (CYSet s g) = CYSet s (f . g) 

main = putStrLn . show 
    $ lowerCYSet 
    $ fmap (\x -> x `mod` 3) 
    $ fmap abs 
    $ fmap (\x -> x - 5) 
    $ liftCYSet $ Set.fromList [1..10] 
-- prints "fromList [0,1,2]"