Параллели типов произведения и суммы в классах типов Haskell

Похоже, что такие классы типов, как Applicative, Monad и Arrow имеют своего рода эквивалент типа суммы в классах типов, таких как Альтернативный, MonadPlus и ArrowPlus соответственно. Например, Applicative и Alternative можно использовать для определения следующего:

(<&&>) :: Applicative f => f a -> f b -> f (a, b)
a <&&> b = (,) <$> a <*> b

(<||>) :: Alternative f => f a -> f b -> f (Either a b)
a <||> b = (Left <$> a) <|> (Right <$> b)

Однако во всех этих случаях (а также с ArrowChoice) , класс типа продукта является необходимым условием для класса типа суммы. Существуют ли правила классов типов или общие функции, которые зависят от класса предварительных требований? Typeclassopedia затрагивает эти отношения, но, к сожалению, я не смог найти какой-либо явной причины такой зависимости.


typeclass haskell arrows applicative alternative-functor
person David Harrison    schedule 29.04.2015    source источник
comment
Возможно, невозможно быть Суммой, не будучи Продуктом, но быть Суммой в одиночку возможно.   -  person AJF    schedule 29.04.2015

Ответы (1)


arrow_upward
6
arrow_downward

Arrow в основном является классом для моноидальных категорий1 с моноидом, не относящимся к Monoid, а продукт-моноид типов Haskell. То есть с единичным элементом () и умножением (,). Итак, типы суммы также составляют моноид, и это то, что использует ArrowChoice. Эти два класса в этом смысле дополняют друг друга; ArrowChoice не должен быть подклассом Arrow.

В моноидальной категории вы можете использовать моноидальные функторы. Как они получаются, зависит от того, что вы используете в качестве моноида типа. За (), (,) вы получаете

class ProdMonoidalFtor f where
  prodUnit :: () -> f ()
  prodZip :: (f a, f b) -> f (a,b)

type (+) = Either
class SumMonoidalFtor f where
  sumUnit :: Void -> f Void
  sumZip :: f a + f b -> f (a+b)

Оказывается, последнее в принципе бесполезно, потому что Void — это начальный объект Hask, то есть существует ровно один Void -> a (а именно absurd) для всех типов a. Однако есть смысл в комоноидальных функторах с +:

class SumCoMonoidalFtor f where
  sumCounit :: f Void -> Void -- I bet you find this useless too, but it's not totally.
  sumCozip :: f (a+b) -> f a + f b

Это, в свою очередь, не имело бы смысла для типов продуктов, поскольку () — это объект терминал.

Что интересно, так это то, что ProdMonoidalFtor эквивалентно Applicative:

instance (ProdMonoidalFtor f) => Applicative f where
  pure x = fmap (const x) $ prodUnit ()
  fs <*> xs = fmap (\(f,x) -> f x) $ prodZip (fs,xs)

Тогда можно было бы заподозрить, что Alternative эквивалентно SumMonoidalFtor, но это не так! На самом деле, это эквивалентно решающим функторам, которые комонады так же, как аппликативы монад.

В то время как Alternative и MonadPlus на самом деле не имеют большой математической поддержки, они, по сути, являются тем, что вы получаете, когда не-Клейсли класс ArrowChoice, но используете категорию Клейсли, которая возникает из ProdMonoidalFtor. Все как-то сомнительно.

1Учитываются только first/left, second/right и ***/+++. Что касается остальных &&&, ||| и arr, они более специфичны и принадлежат IMO в отдельных классах.

person leftaroundabout    schedule 29.04.2015
comment
sumZip также бессмысленно, так как вы можете иметь either (fmap Left) (fmap Right), верно? - person chi; 29.04.2015
comment
@chi: Думаю, да, но я не уверен в доказательствах. - person leftaroundabout; 29.04.2015