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

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

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

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

Но поскольку я использую функцию _ 7_ это приводит к ограничению класса, вызывающему для типов, используемых в 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

См. Живой пример

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

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

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


haskell type-constructor
person Miguel    schedule 16.10.2012    source источник

Ответы (3)


arrow_upward
15
arrow_downward

К сожалению, нет простого способа сделать это с помощью стандартного класса 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: пример Foldable, который не является Functor (или не Traversable)? есть хорошее обсуждение этого.

person Tikhon Jelvis    schedule 16.10.2012
comment
Одна из проблем с ограниченными классами функторов заключается в том, что мы теряем много мощности. Мы часто хотим помещать в них функции, особенно с аппликативными функторами. Однако во многих случаях невозможно предоставить общие экземпляры интересующих нас классов для функций. - person hammar; 16.10.2012

arrow_upward
2
arrow_downward

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

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

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

person Ben Millwood    schedule 25.10.2012

arrow_upward
0
arrow_downward

Вы можете сделать это с помощью 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]"
person SeongChan Lee    schedule 15.11.2017