Моноидальные функторы Лакса с другой моноидальной структурой

"Изящное альтернативное представление" для Applicative основано на следующих двух эквивалентностях

pure a = fmap (const a) unit
unit = pure ()

ff <*> fa = fmap (\(f,a) -> f a) $ ff ** fa
fa ** fb = pure (,) <*> fa <*> fb

Уловка для получения этого «аккуратного альтернативного представления» для Applicative такая же, как и уловка для zipWith - заменить явные типы и конструкторы в интерфейсе вещами, в которые можно передать тип или конструктор, чтобы восстановить исходный интерфейс.

unit :: f ()

Заменяется на pure, в который мы можем подставить тип () и конструктор () :: () для восстановления unit.

pure :: a  -> f a
pure    () :: f ()

И аналогично (хотя и не так просто) для замены типа (a,b) и конструктора (,) :: a -> b -> (a,b) на liftA2 для восстановления **.

liftA2 :: (a -> b -> c) -> f a -> f b -> f c
liftA2    (,)           :: f a -> f b -> f (a,b)

Затем Applicative получает красивый оператор <*>, помещая приложение-функцию ($) :: (a -> b) -> a -> b в функтор.

(<*>) :: f (a -> b) -> f a -> f b
(<*>) = liftA2 ($)

Чтобы найти "аккуратную альтернативную презентацию" для PtS, нам нужно найти

• что-то мы можем заменить тип Void на, чтобы восстановить unit
• что-то, что мы можем заменить тип Either a b и конструкторы Left :: a -> Either a b и Right :: b -> Either a b, чтобы восстановить **

(Если вы заметили, что у нас уже есть что-то, что конструкторы Left и Right могут быть переданы, вы, вероятно, сможете понять, чем мы можем заменить **, не выполняя шаги, которые я использовал; я не заметил этого, пока не решил это)

единица измерения

Это сразу дает нам альтернативу unit для сумм:

empty :: f a
empty = fmap absurd unit

unit :: f Void
unit = empty

оператор

Мы хотим найти альтернативу (**). Существует альтернатива суммам типа Either, которая позволяет записывать их как функции продуктов. Он проявляется как шаблон посетителя в объектно-ориентированных языках программирования, где суммы не существуют.

data Either a b = Left a | Right b

{-# LANGUAGE RankNTypes #-}
type Sum a b = forall c. (a -> c) -> (b -> c) -> c

Это то, что вы получите, если измените порядок аргументов either и частично примените их.

either :: (a -> c) -> (b -> c) -> Either a b -> c

toSum :: Either a b -> Sum a b
toSum e = \forA forB -> either forA forB e

toEither :: Sum a b -> Either a b
toEither s = s Left Right

Мы видим, что Either a b ≅ Sum a b. Это позволяет нам переписать тип для (**)

(**) :: f a -> f b -> f (Either a b)
(**) :: f a -> f b -> f (Sum a b)
(**) :: f a -> f b -> f ((a -> c) -> (b -> c) -> c)

Теперь понятно, что делает **. Он задерживает fmap привязку чего-либо к обоим своим аргументам и объединяет результаты этих двух сопоставлений. Если мы введем новый оператор <||> :: f c -> f c -> f c, который просто предполагает, что fmaping уже был выполнен, то мы увидим, что

fmap (\f -> f forA forB) (fa ** fb) = fmap forA fa <||> fmap forB fb

Или вернемся к Either:

fa ** fb = fmap Left fa <||> fmap Right fb
fa1 <||> fa2 = fmap (either id id) $ fa1 ** fa2

Таким образом, мы можем выразить все, что PtS может выразить с помощью следующего класса, и все, что может реализовать PtS, может реализовать следующий класс:

class Functor f => AlmostAlternative f where
    empty  :: f a
    (<||>) :: f a -> f a -> f a

Это почти наверняка то же самое, что и класс Alternative, за исключением того, что мы не требовали, чтобы Functor был Applicative.

Вывод

Это просто Functor, Monoid для всех типов. Это было бы эквивалентно следующему:

class (Functor f, forall a. Monoid (f a)) => MonoidalFunctor f

Ограничение forall a. Monoid (f a) - это псевдокод; Я не знаю способа выразить подобные ограничения в Haskell.

Прежде чем говорить о моноидальных функторах, вам необходимо убедиться, что вы находитесь в моноидальной категории. Так получилось, что Hask является моноидальной категорией следующим образом:

• () как личность
• (,) как бифунктор
• Определите изоморфные типы, то есть (a,()) ≅ ((),a) ≅ a и (a,(b,c)) ≅ ((a,b),c).

Как вы заметили, это также моноидальная категория, когда вы обмениваете () на Void и (,) на Either.
Однако моноидальная категория не уведет вас очень далеко - Hask настолько мощен, что он декартово закрыто. Это дает нам каррирование и связанные с ним техники, без которых аппликатив был бы бесполезен.

Моноидальная категория может быть декартово замкнутой, если ее идентичность - терминальный объект, то есть тип на, где существует ровно одна (мы, конечно, не принимаем во внимание ⟂) стрелку. Для любого типа A существует одна функция A -> (), а именно const (). Однако функции A -> Void нет. Вместо этого Void является начальным объектом: существует ровно одна стрелка от, а именно метод absurd :: Void -> a. Тогда такая моноидальная категория не может быть декартово замкнутой.
Теперь, конечно, вы можете легко переключаться между начальной и конечной, поворачивая направление стрелки. Это всегда помещает вас в двойную структуру, поэтому мы получаем кокартезианскую закрытую категорию . Но это означает, что вам также нужно перевернуть стрелки в ваших моноидальных функторах. Они называются решающими функторами, затем (и обобщают комонады ). Благодаря удивительной схеме именования Конора,

class (Functor f) => Decisive f where
  nogood :: f Void -> Void
  orwell :: f (Either s t) -> Either (f s) (f t)

Мой опыт в теории категорий очень ограничен, но, черт возьми, ваш класс PtS напоминает мне _ 1_ class, которая выглядит примерно так:

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

Единственная проблема, конечно же, в том, что Alternative является расширением Applicative. Однако, возможно, можно представить, что это представлено отдельно, и тогда комбинация с Applicative очень напоминает функтор с некоммутативной кольцевой структурой с двумя моноидными структурами в качестве операций кольца? Между Applicative и Alternative IIRC также действуют законы о распределении.