Ograniczenia parametrów typu dla typów czcionek z typem * -> *

Question

Załóżmy, że mam typ Heap a, gdzie Heap jest konstruktorem typu * -> *. Wiele podstawowych operacji na stercie wymaga, aby typ a był instancją klasy typu Ord.

data Heap a = ... 

findMin :: Ord a => Heap a -> a 
deleteMin :: Ord a => Heap a -> Heap a 

Chcę zadeklarować moje Heap typ jako przykład Foldable klasy typu jak najszybciej a typ parametr jest instancją klasy Ord typu (będzie to łatwe, aby wyrazić poprzez findMin i deleteMin funkcji).

Ten rodzaj relacji można easely wyrażona gdy mamy do czynienia z klasami typu, które wymagają rodzaju rodzaju *, jak Show:

instance Show a => Show (Heap a) where 
    show h = ... 

Ale mam problemy z deklaracją z Foldable:

instance Foldable Heap where 
    -- Ouch, there is no `a` type parameter to put the constraint on! 
    foldr f z h = ... 

Czy jest możliwe umieszczenie ograniczenia na parametrze typu a w takiej deklaracji wystąpienia?

Answer 1

Ogólnie rzecz biorąc, nie, gdy konstruktorowi typu nadano instancję, nie można ograniczyć typów, do których został zastosowany. Przeważnie jest to dobre, ponieważ zapewnia to np. Functor instancje są naprawdę agnostyczne w odniesieniu do ich rodzaju elementu, co pomaga zachować ładne i przewidywalne zachowanie w sposób miły i przewidywalny.

Czasami jest to uciążliwość, a najpowszechniejszym przykładem jest rzeczywiście konieczność ograniczenia Ord dla uporządkowanej struktury danych, która mogłaby być przyjemną, dobrze zachowaną instancją.

Istnieje kilka technik eksperymentalnych obejmujących takie elementy, jak ograniczenia, ale w konkretnym przypadku istnieje już możliwe rozwiązanie. Jeśli spojrzysz na definicję Foldable, oznacza to, że musisz wdrożyć tylko foldMap lub foldr, więc rozważymy to. Uwaga typy:

foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m 
foldr :: (Foldable t) => (a -> b -> b) -> b -> t a -> b 

W obu przypadkach, typ z instancją Foldable pojawia się tylko raz, jako argument funkcji. Z tego powodu można use GADTs z Ord przymusu:

data Heap a where 
    Heap :: (Ord a) => ... 

Dzięki temu, będziesz potrzebować instancję Ord każdej chwili tworzonych wartość Heap, nawet pusty sterty; ale kiedy otrzymasz , otrzymasz wartość a Heap, dopasowanie do wzoru spowoduje powrót instancji Ord z powrotem do zakresu - nawet wewnątrz instancji Foldable!

Należy pamiętać, że to nie pomaga w wielu innych sytuacjach:

fmap :: (Functor f) => (a -> b) -> f a -> f b 

Tutaj możemy uzyskać instancji Ord na a, ale że również potrzebny dla b, co nie jest możliwe.

return :: (Monad m) => a -> m a 

Tutaj musimy dostarczyć także instancję Ord.

Answer 2

Zapoznaj się z biblioteką keys w witrynie Hackage. Sprawdź, czy jego klasa typu FoldableWithKey jest tym, czego potrzebujesz.