Лёкс-моноидальные функторы с различной моноидальной структурой

Аппликативные функторы хорошо известны и хорошо любимы среди Haskellers за их способность применять функции в эффективном контексте.

В теоретико-множественных терминах можно показать, что методы Applicative:

pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b

эквивалентны наличию a Functor f с операциями:

unit :: f ()
(**) :: (f a, f b) -> f (a,b)

идея состоит в том, что для написания pure вы просто заменяете () в unit заданным значением, а для записи (<*>) вы хлюпаете функцию и аргумент в кортеж, а затем сопоставляете подходящую функцию приложения над ним.

Более того, это соответствие превращает законы Applicative в естественные моноидальные законы о unit и (**), поэтому на самом деле аппликативный функтор - это то, что теоретик категории назвал бы слабым моноидальным функтором (lax, потому что (**) является просто естественным преобразованием, а не изоморфизмом).

Хорошо, отлично, отлично. Это хорошо известно. Но это только одно семейство слабых моноидальных функторов - тех, которые относятся к моноидальной структуре продукта. Слабый моноидальный функтор включает в себя два варианта моноидальной структуры в источнике и предназначении: вот что вы получаете, если вы превращаете продукт в сумму:

class PtS f where
  unit :: f Void
  (**) :: f a -> f b -> f (Either a b)

-- some example instances
instance PtS Maybe where
  unit = Nothing
  Nothing ** Nothing = Nothing
  Just a ** Nothing = Just (Left a)
  Nothing ** Just b = Just (Right b)
  Just a ** Just b = Just (Left a) -- ick, but it does satisfy the laws

instance PtS [] where
  unit = []
  xs ** ys = map Left xs ++ map Right ys

Кажется, что превращение суммы в другие моноидальные структуры становится менее интересным, поскольку unit :: Void -> f Void определяется однозначно, поэтому вы действительно имеете больше полугруппы. Но все же:

  • Существуют ли другие слабые моноидальные функторы, подобные описанным выше или полезным?
  • Есть ли опрятная альтернативная презентация для них, например, Applicative one?

Ответы

Ответ 1

"Чистая альтернативная презентация" для 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, который просто предполагает, что fmap ing уже был выполнен, то мы можем видеть, что

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.

Ответ 2

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

  • () как идентификатор
  • (,) как bifunctor
  • Идентифицировать изоморфные типы, т.е. (a,()) ≅ ((),a) ≅ a и (a,(b,c)) ≅ ((a,b),c).

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

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

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

Ответ 3

Мой опыт в теории категорий очень ограничен, но FWIW, ваш класс PtS напоминает мне Alternative class, который выглядит по существу как это:

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

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