W jaki sposób można wykonać wiązanie klasy w instancji klasy, która wymaga konstruktora typu, a nie konkretnego typu?

Question

Obecnie jestem w Chapter 8 z Learn you a Haskell i dotarłem do sekcji na typeclass Functor. W tej sekcji autor podaje przykłady, jak różne typy mogą być tworzone wystąpienia klasy (np. Maybe, niestandardowy Tree itp.) Widząc to, postanowiłem (dla zabawy i praktyki) spróbuj wdrożyć instancję dla typu Data.Set ; w tym wszystkim oczywiście ignorując Data.Set.map.

Sam rzeczywisty przypadek jest dość prosta, a ja napisałem to jako:

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

Ale ponieważ zdarza mi się korzystać z funkcji fromList Daje to w ograniczeniu klasy wzywając do rodzajów stosowanych w Set być Ord, jak to wytłumaczyć błąd kompilatora:

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 

Patrz: Live Example

I tri ed nałożenie ograniczenia na instancję lub dodanie sygnatury typu do fmap, ale żadna z nich nie powiodła się (obie były również błędami kompilatora).

Jak w takiej sytuacji można spełnić i zaspokoić przymus? Czy jest jakiś możliwy sposób?

Z góry dziękuję! :)

Answer 1

Niestety, jest no łatwy sposób to zrobić ze standardową klasą Functor. Dlatego domyślnie Set nie jest dostarczany z instancją Functor: nie można jej napisać.

Jest to problem, a niektóre sugerowane rozwiązania (np. Definiowanie klasy Functor w inny sposób), ale nie wiem, czy istnieje zgoda, jak najlepiej sobie z tym poradzić.

wierzę jedno podejście jest przepisać klasę Functor korzystając constraint kinds do zreifikować dodatkowych ograniczeń wystąpień nowego Functor klasy mogą mieć. To pozwoli ci określić, że Set musi zawierać typy z klasy Ord.

Inne podejście wykorzystuje tylko klasy wieloparametrowe. Mogłem tylko znaleźć artykuł o tym, jak to zrobić dla klasy Monad, ale sprawienie, że Set część z Monad napotyka na te same problemy, co uczynienie jej częścią Functor. Nazywa się Restricted Monads.

Podstawowa Istota pomocą klas wielu parametrów tutaj wydaje się być coś takiego:

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 

Zasadniczo, wszystko co robisz tutaj robi typy wSet również częścią klasy . Pozwala to ograniczyć to, jakie typy mogą występować podczas pisania instancji tej klasy.

Ta wersja Functor wymaga dwóch rozszerzeń: MultiParamTypeClasses i FlexibleInstances.(Trzeba pierwszego rozszerzenia, aby móc określić klasę i drugiego rozszerzenia, aby móc określić instancję dla Set.)

Haskell : An example of a Foldable which is not a Functor (or not Traversable)? ma dobrą dyskusję na ten temat.

Answer 2

To niemożliwe. Celem klasy Functor jest to, że jeśli masz Functor f => f a, możesz zamienić a na co tylko chcesz. Klasa nie może ograniczać cię tylko do zwrotu tego lub tamtego. Ponieważ Set wymaga, aby jego elementy spełniały pewne ograniczenia (i rzeczywiście nie jest to szczegół implementacji, ale naprawdę istotna właściwość zestawów), nie spełnia wymagań Functor.

Istnieją, jak wspomniano w innej odpowiedzi, sposoby rozwijania klasy takiej jak Functor, która ogranicza Cię w ten sposób, ale to naprawdę inna klasa, ponieważ daje użytkownikowi klasy mniej gwarancji (nie masz użyj tego przy dowolnym parametrze, jaki chcesz), w zamian za zastosowanie do szerszego zakresu typów. Jest to przecież klasyczny kompromis definiujący właściwość typów: im więcej typów chcesz spełnić, tym mniej muszą być zmuszeni do zaspokojenia.

(Innym ciekawym przykładem, gdzie ten pokazuje się to klasa MonadPlus. W szczególności, dla każdej instancji MonadPlus TC można dokonać instancją Monoid (TC a), ale nie zawsze można iść na odwrót. Stąd wystąpienie Monoid (Maybe a) różni z instancji MonadPlus Maybe, ponieważ te pierwsze mogą ograniczać a ale ten ostatni nie może.)

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]"