Как можно утверждать ограничение класса в экземпляре класса, для которого требуется конструктор типа, а не конкретный тип?

В настоящее время я в Глава 8 Учите вас Haskell, и я дошел до раздела на Functor typeclass. В этом разделе автор приводит примеры того, как могут быть созданы различные типы экземпляров класса (например, Maybe, пользовательский тип Tree и т.д.). Увидев это, я решил (для удовольствия и практики) попробовать реализовать экземпляр для Data.Set; во всех этих случаях, конечно, игнорируя Data.Set.map.

Фактический экземпляр сам по себе довольно прямолинейный, и я написал его как:

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

Но, поскольку я использую функцию fromList, это приводит к ограничению класса, вызывающему типы, используемые в Set быть Ord, что объясняется ошибкой компилятора:

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

Смотрите: Пример Live

Я попытался установить ограничение на экземпляр или добавить подпись типа к fmap, но ни одно из них не удалось (оба были ошибками компилятора.)

Учитывая такую ситуацию, как можно выполнить и удовлетворить ограничение? Есть ли способ?

Спасибо заранее!:)

Ответ 1

К сожалению, нет простого способа сделать это со стандартным классом Functor. Вот почему Set не поставляется с экземпляром Functor по умолчанию: вы не можете его написать.

Это что-то вроде проблемы, и были некоторые предлагаемые решения (например, определение класса Functor по-другому), но я не знаю, существует ли консенсус относительно того, как наилучшим образом справиться с этим.

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

В другом подходе используются только многопараметрические классы. Я могу найти статью о том, как это сделать для класса Monad, но сделать Set часть Monad сталкивается с теми же проблемами, что и сделать ее частью Functor. Он называется Ограниченные монады.

Основной смысл использования многопараметрических классов здесь выглядит примерно так:

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

По существу, все, что вы делаете здесь, делает типы в Set также частью класса. Это позволяет вам ограничить то, что эти типы могут быть, когда вы пишете экземпляр этого класса.

Эта версия Functor требует двух расширений: MultiParamTypeClasses и FlexibleInstances. (Чтобы иметь возможность определить класс и второе расширение, вам нужно, чтобы первое расширение имело возможность определить экземпляр для Set.)

Haskell: Пример складки, который не является Functor (или не Traversable)?, хорошо обсуждает это.

Ответ 2

Это невозможно. Цель класса Functor заключается в том, что если у вас есть Functor f => f a, вы можете заменить a на что угодно. Класс не позволяет ограничивать вас только тем, что он возвращает. Поскольку Set требует, чтобы его элементы удовлетворяли определенным ограничениям (и, действительно, это не деталь реализации, а действительно существенное свойство множеств), он не удовлетворяет требованиям Functor.

Есть, как упоминалось в другом ответе, способы разработки класса, такого как Functor, который ограничивает вас таким образом, но это действительно другой класс, поскольку он дает пользователю класса меньше гарантий (вы не знаете, t использовать это с любым параметром типа, который вы хотите), в обмен на то, чтобы стать применимым к более широкому диапазону типов. То есть, в конце концов, классический компромисс определения свойства типов: чем больше типов вы хотите его удовлетворить, тем меньше они должны быть вынуждены удовлетворять.

(Еще один интересный пример того, где это показано, - это класс MonadPlus. В частности, для каждого экземпляра MonadPlus TC вы можете создать экземпляр Monoid (TC a), но вы не всегда можете пойти наоборот. экземпляр Monoid (Maybe a) отличается от экземпляра MonadPlus Maybe, поскольку первый может ограничить a, но последний не может.)

Ответ 3

Вы можете сделать это, используя 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]"