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

Question

Предположим, у меня есть тип Pair:

data Pair a = Pair a a

Как правильно написать для него экземпляр монады? Моя идея примерно такая:

instance Semigroup a => Semigroup (Pair a) where
  Pair a1 a2 <> Pair b1 b2 = Pair (a1 <> b1)(a2 <> b2)

instance Monad Pair where
  return = pure
  (Pair a b) >>= f = f a <> f b

Это правильно? Если так, то где указать, что b-тип в паре b является полугруппой?

Answer 1

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

instance Monad Pair where
    m >>= f = joinPair (f <$> m)

joinPair :: Pair (Pair a) -> Pair a
joinPair (Pair (Pair x _) (Pair _ y)) = Pair x y

Причина, по которой это правильный экземпляр монады, заключается в том, что Pair является представимым функтором .

instance Representable Pair where
    type Rep Pair = Bool

    index (Pair x _) False = x
    index (Pair _ y) True  = y

    tabulate f = Pair (f False) (f True)

Оказывается, для каждого представимого функтора (>>=) эквивалентна следующей bindRep функции.

bindRep :: Representable f => f a -> (a -> f b) -> f b
bindRep m f = tabulate (\a -> index (f (index m a)) a)

Если мы специализируемся на bindRep функция к Pair мы получаем следующее.

bindRep :: Pair a -> (a -> Pair b) -> Pair b
bindRep (Pair x y) f = tabulate (\a -> index (f (index (Pair x y) a)) a)
                     = Pair (index (f x) False) (index (f y) True)
--                          |_________________| |________________|
--                                   |                   |
--                           (1st elem of f x)   (2nd elem of f y)

Следующая запись в блоге Адельберта Чанга объясняет это лучше. Рассуждение с представимыми функторами .

Answer 2

Функтор и аппликативные экземпляры просты. Экземпляр монады занял у меня некоторое время.

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

instance Functor Pair where 
  fmap f (Pair a b) = Pair (f a) (f b)

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

instance Monad Pair where 
  return = pure
  (Pair a b) >>= f = let Pair a' _ = f a 
                         Pair _ b' = f b
                     in  Pair a' b'

Я пришел к этому решению, применив законы монады. Вы можете легко проверить пример, который не действует в законе об идентичности, если вы берете Pair a' a'' или Pair b' b'' или Pair a' b' или Pair a'' b''. Таким образом, единственные решения должны быть в диагонали. Определив

(m >>= f) = Pair (first . f . first $ m) (second . f . second $ m)

, где first и second являются очевидными, вы можете проверить все законы.

Answer 3

Можно превратить Pair в Monad, имея join, который принимает диагональ квадрата 2 × 2. return не имеет другого выбора, кроме как повторить свой аргумент. Это превращает Pair в по существу фиксированную длину ZipList.

Конечно, это определение join отбрасывает некоторые данные. Это может или не может быть важно.

Answer 4

Экземпляр Monad может не накладывать никаких ограничений на тип данных, которые он содержит (a здесь). Он должен рассматривать эти данные как полностью непрозрачные. Я не думаю, что ваш тип Pair допускает экземпляр Monad (или Applicative), потому что нет способа превратить пару пар в одну пару без потери некоторых данных или использования их каким-либо образом не разрешеннымпо определению класса типов.