Представимый функтор, изоморфный (Bool -> a) - PullRequest
Новая
       26

Представимый функтор, изоморфный (Bool -> a)

15 голосов
/ 30 мая 2011

Я подумал, что попробую интригующий пакет Представимые-функторы , чтобы определить экземпляр Monad и Comonad для функтора, заданного data Pair a = Pair a a, который представлен Bool;как упоминалось в ответе на мой предыдущий вопрос о векторной монаде .

Первое, что я заметил, было то, что для того, чтобы сделать мой тип экземпляром Representable, я должен не только определять tabulate и index, но также убедитесь, что мой тип является экземпляром классов типов Indexable, Distributive, Keyed, Apply, Applicative и Functor.Ну, ладно, index завершает определение Indexable, а функция <.> Apply может использовать <*> из Applicative;и не должно быть сюрпризом, что требуется экземпляр Functor.Тем не менее, я сомневаюсь, что мои экземпляры для Keyed и Distributive. 

data Pair a = Pair a a
  deriving (Show,Eq)

instance Functor Pair where
  fmap f (Pair x y) = Pair (f x) (f y)

type instance Key Pair = Bool

instance Keyed Pair where
  mapWithKey f (Pair x y) = Pair (f False x) (f False y)

instance Indexable Pair where
  index (Pair x _) False = x
  index (Pair _ y) True  = y

instance Applicative Pair where
  pure a = Pair a a
  Pair f g <*> Pair x y = Pair (f x) (g y)

instance Apply Pair where
  (<.>) = (<*>)

instance Distributive Pair where
  collect f x = Pair (getL . f <$> x) (getR . f <$> x)
    where getL (Pair x _) = x
          getR (Pair _ y) = y

instance Representable Pair where
  tabulate f = Pair (f False) (f True)

Мое mapWithKey определение заимствует из определения [] для Keyed: хотя я этого не делаюпонять, почему 0 использовался там для каждой итерации.Я также использовал False для каждого члена Pair.

. Как я сделал вывод, определив экземпляры Monad и Comonad, я обнаружил, что Bool требует определения Semigroup для Extend и Monoid определение для Comonad.Я следую за экземпляром Semigroup для Either, который изоморфен (||), и выбираю False для mempty: 

instance Monad Pair where
  return = pureRep
  (>>=)  = bindRep

instance Monoid Bool where
  mempty = False
  mappend = (||)

instance Semigroup Bool where
  (<>) = mappend

instance Extend Pair where
  extend = extendRep -- needs Bool Semigroup

instance Comonad Pair where
  extract = extractRep -- needs Bool Monoid

Итак, я выполнил требованияRepresentable класс правильно, идиоматически?

1 Ответ

15 голосов
/ 30 мая 2011

Да, у вас есть. Хотя ваш экземпляр для Keyed выключен. 

instance Keyed Pair where
    mapWithKey f (Pair x y) = Pair (f False x) (f True y)

или даже проще 

instance Keyed Pair where
    mapWithKey = mapWithKeyRep

и аналогично 

instance Distributive Pair where
    distribute = distributeRep

Учитывая index и tabulate, вы можете использовать различные методы fooRep в модуле Representable, чтобы предоставить определения для всех других суперклассов.

Определения Extend и Comonad на самом деле не являются частью требований, которые должны быть Representable. Они включены, тем не менее, потому что представимость означает, что вы изоморфны функции, которая позволяет вам переопределить определение для «экспоненциального» * ​​1020 * (он же cowriter, или Traced comonad), чтобы стать Comonad также, учитывая некоторый моноид на вашем представлении. Это не требуется, хотя, главным образом потому, что я не могу ограничить его, учитывая используемые типы.

Возможно, вы захотите сбросить Semigroup и Monoid для Bool, хотя и просто ручные инструменты extend и extract. Это достаточно просто. 

instance Extend Pair where
    extend f p@(Pair a b) = Pair (f p) (f (Pair b a))

instance Comonad Pair where
    extract (Pair a b) = a

Кроме того, этот тип предоставляется пакетом представимые попытки , который включает в себя ряд других экземпляров.

И 

import Control.Applicative
bool = [True, False]
f tt _tf _ft _ff True  True  = tt
f _tt tf _ft _ff True  False = tf
f _tt _tf ft _ff False True  = ft
f _tt _tf _ft ff False False = ff
associative f = and (assoc <$> bool <*> bool <*> bool) where 
    assoc a b c = f (f a b) c == f a (f b c)
semigroups = filter associative 
    [ f tt tf ft ff | tt <- bool, tf <- bool, ft <- bool, ff <- bool ]
unital (u, f) = all unit bool where 
    unit a = f u a == a && f a u == a
monoids = filter unital 
    [ (u, f) | u <- bool, f <- semigroups ]

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

...