Введите ограничения параметров для экземпляров типов с видом * → *

Предположим, что у меня есть Heap a типа, где Heap является конструктором типа вида * → *. Многие основные операции по куче требуют a типе, чтобы быть экземпляром Ord класса типа.

data Heap a = ...

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

Я хочу, чтобы объявить мой Heap типа как экземпляр Foldable классы типа, как только параметр типа является экземпляром a Ord класса типа (это будет легко выразить через findMin и deleteMin функции).

Такое отношение можно легко выразить, когда мы имеем дело с типами классов, которые требуют типа вида *, например Show:

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

Но у меня проблемы с декларированием Foldable:

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

Можно ли ставить ограничение на a параметре типа в таком объявлении экземпляра?

Ответы

Ответ 1

В общем случае нет, когда самому конструктору типа предоставляется экземпляр, нет способа ограничить типы, к которым он применяется. В основном это хорошо, так как это гарантирует, что, например, экземпляры Functor действительно агностически относятся к типу элементов, что помогает сохранять приятное и предсказуемое поведение приятным и предсказуемым.

Иногда это раздражает, и наиболее распространенный пример действительно Ord ограничения Ord для сортированной структуры данных, которая в противном случае могла бы быть хорошим, хорошо выполненным экземпляром.

Существуют некоторые экспериментальные методы, включающие такие вещи, как типы ограничений, но в вашем конкретном случае уже существует жизнеспособное решение. Если вы посмотрите на определение Foldable, в нем говорится, что нужно выполнить только foldMap или foldr, поэтому мы рассмотрим их. Обратите внимание на типы:

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

В обоих случаях тип с экземпляром Foldable появляется только один раз, как аргумент функции. Из-за этого вы можете использовать GADT с ограничением Ord:

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

Делая это, вам понадобится экземпляр Ord при создании значения Heap, даже пустой кучи; но когда вы получите значение " Heap, сопоставление шаблонов на нем приведет к возврату экземпляра Ord в область видимости - даже внутри экземпляра Foldable !

Обратите внимание, что это не помогает во многих других ситуациях:

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

Здесь мы можем получить экземпляр Ord для a, но нам также понадобится один для b, что невозможно.

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

Здесь нам также нужно предоставить экземпляр Ord.

Ответ 2

Взгляните на библиотеку keys в Hackage. Проверьте, подходит ли его класс типа FoldableWithKey.