Что такое кокартезианский комоноид и что такое кокартезианский комоноидальный функтор?

Question

В последнее время я экспериментировал с моноидами и дистрибутивами и думаю, что нашел кое-что интересное (описано в моем ответе) - это уже известные структуры? (Мне не удалось найти какие-либо ссылки на них в Интернете, и я не думаю , что упустил какую-то причину, по которой они были бы бессмысленными)

Если они не были известны ранее, кажутся ли они полезными или интересными кому-либо, кроме меня?

Вопросы, которые приводят меня сюда:

1. Что произойдет, если вы поменяете продукты на суммы в комоноидах?
2. Что произойдет, если вы поменяете произведения на суммы в комоноидальных функторах (коаппликативах, коальтернативах, соделимых, кодируемых)? (Только несколько ответов на первые два)

Answer 1

В этом ответе (который в идеале я должен был написать незадолго до первой годовщины вопроса, но, увы) я в основном буду придерживаться ковариантных моноидальных функторов, чтобы сохранить управляемость области действия, хотя будет возможность рассмотреть некоторые из них. другие аспекты вопроса и вашего собственного ответа .

Еще один мой редакционный выбор — проявлять сдержанность в использовании слова «co-» для названий вещей. И дело не только в том, что легко заблудиться в мешанине префиксов, когда, как вы заметили, существует базовый уровень из шестнадцати гипотетических классов моноидальных функторов, но также и потому, что для каждого из них обычно существует более одного правдоподобного кандидата на роль «коэффициента». -" прозвище. Например, рассмотрим (приведенные к стандартным сигнатурам моноидального функтора):

      class Functor f => Applicative f where
    zipped :: (f a, f b) -> f (a, b)
    unit :: () -> f ()
    -- zipped = uncurry (liftA2 (,))
    -- unit = const (pure ())

Можно было бы принять в качестве «коаппликативного» его простой моноидальный аналог oplax , полученный переключением с Hask на Hask^op (и, таким образом, поворотом стрелок методов), сохраняя при этом тензорное произведение:

      class Functor f => Unzip f where
    unzip :: f (a, b) -> (f a, f b)
    trivialU :: f () -> ()

Эти комбинаторы имеют законную реализацию для каждого , сunzip = fmap fst &&& fmap sndиtrivialU = const (). Примечательно, что это коаппликатив, на который ссылается , где отмечается, что дистрибутивная документация:

Из-за отсутствия нетривиальных комоноидов в Haskell мы можем ограничиться требованием функтора, а не какого-либо коаппликативного класса.

Помимо тривиальностиUnzipЕще одно правдоподобное возражение против того, чтобы называть его коаппликативным, состоит в том, что тщательная дуализация аппликатива должна также заменить (продукт в Hask) на (продукт в Hask^op). Это приведет к вашему классу, который я покажу здесь в презентации, заимствованной из сообщения Конора МакБрайда :

      class Functor f => Decisive f where
    orwell :: f (Either a b) -> Either (f a) (f b)
    nogood :: f Void -> Void

(Стоит отметить, что аналогичные вопросы возникают и при переходе от ковариантных функторов к контравариантным. При заменеFunctorсContravariantв сигнатурах приводит к , если тензорные произведения также дуализированы совместимым образом, вместо этого мы получим. Более того, как утверждается в моей статье в блоге «Делимый и моноидальный квартет» ,Decidableзеркала более близко, чемDivisible.)

Хотя на первый взгляд может показаться, что только функторы, имеющие ровно одно значение, могут быть , это справедливо только в том случае, если мы требуем, чтобы они были изоморфизмом. В частности, как подчеркивает Макбрайд, можно создать любую комонаду (или, по сути, любой функтор, роль которого играет что-то):

      orwellW :: Comonad w => w (Either a b) -> Either (w a) (w b)
orwellW u = case extract u of
    Left a -> Left $ either id (const a) <$> u
    Right b -> Right $ either (const b) id <$> u

nogoodW :: Comonad w => w Void -> Void
nogoodW = extract

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

      import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as N

redact :: (a -> Bool) -> a -> [a] -> [a]
redact p d = N.tail . either id id . orwellW . (Right d :|) . map classify
    where
    classify a = if p a then Right a else Left a

      ghci> redact (>= 0) 0 [5,-2,3,0,-1,4] 
[5,0,3,0,0,4]

В этой реализацииclassifyиспользует предикат для создания косеполугруппы на основе - (другими словами, законного экземпляра вашегоSplit).orwellWподнимает эту кополугруппу до непустого списка (предполагая, что ради последовательностиp dявляетсяTrue).

(кстати, это также напоминает, как можно реализовать zip-дополнение через подходящий экземпляр для непустых списков, как показано в этом ответе , кстати, также написанном МакБрайдом, хотя на данный момент я не уверен, как действительно глубокие отношения.)

О связях между /Matchable,TraversableиDistributive, я считаю, что они сводятся к тому, что все функторы, имеющие ровно одно значение (левые сопряженные эндофункторы Hask или ваш ), являются комонадами, и, таким образом, . Что касается этих вопросов, то менее мощный дистрибутив, который вы предлагаете, в конечном итоге будет простоFTraversable(вталкивая левое сопряженное внутрь, а не вытягивая правое сопряженное наружу), и прямо сейчас я не понимаю, как это можно обобщить до .

---

Теперь давайте посмотрим. Стандартное представление моноидального функтора может быть таким:

      class Functor f => Alternative f where
    combined :: (f a, f b) -> f (Either a b)
    nil :: () -> f Void
    -- combined = uncurry (<|>) . bimap (fmap Left) (fmap Right)
    -- nil = const empty

Поскольку оно нам понадобится через некоторое время, стоит подчеркнуть, что мы можем восстановиться, сняв тривиальное Either-основанный моноид :

      -- either id id :: Either a a -> a
aplus :: (f a, f a) -> f a
aplus = fmap (either id id) . combined

Прямой аналог oplax оказался чем-то знакомым:

      class Functor f => Filterable f where
    partition :: f (Either a b) -> (f a, f b)
    trivialF :: f Void -> ()

На самом деле это эквивалентно знакомому, mapMaybe-основанный на Filterableclass , как подробно описано в разделе « Может ли фильтроваться каждая альтернативная монада?» . В частности, используя подъем косеполугруппы предикатов, проиллюстрированный ранее с помощьюredactведет непосредственно кfilter.

Однако мы еще не дуализировали тензоры. Это приведет к тому, что ваш (иBiasable, но я отказываюсь от идентичности, чтобы иметь обитаемые типы):

      class Functor f => Bias f where
    biased :: f (a, b) -> Either (f a) (f b)

Поднятие тривиального(,)-основанный комоноид дает нам:

      biasing :: f a -> Either (f a) (f a)
biasing = biased . fmap (id &&& id)

предлагает, по крайней мере, классификатор фигур (выдает ли он функториальную форму своего аргумента или зависит от нее), а также связанный с ним выбор между компонентами пары. Я говорю «по крайней мере», потому что отказ от идентичности оставляет только закон ассоциативности, а этот закон не исключает изменений или перестановокf-форму, пока они идемпотентны и сохраняютLeft/Rightклассификация.

Если такое легкое отношение к законам считается проблемой, есть один разумный способ несколько ужесточить его. Чтобы представить это, давайте на мгновение вернемся к и . Хотя формулировка моноидального функтора в принципе не зависит от , существует несколько других возможных законов, которые иногда используются для соединения двух классов и лучшего определения значения (комментарий к этому вопросу см. в ответе Антала Спектора-Забуски на книгу « Смущенный значение класса типа «Альтернативный» и его связь с другими классами типов ). Одним из таких законов является правая дистрибутивность(<*>)над(<|>):

      (u <|> v) <*> w = (u <*> w) <|> (v <*> w)

Мы можем перевести это на словарный запас, который мы здесь используем...

      zipped (aplus (u, v), w) = aplus (zipped (u, w), zipped (v w)

... и сделаем его бесточечным, чтобы было проще манипулировать:

      zipped . first aplus = aplus . bimap zipped zipped . distribR

distribR :: (((a, b), c) -> ((a, c), (b, c))
distribR ((a, b), c) = ((a, c), (b, c))

Теперь, если двойственно к (без идентичности) и двойственен к , мы должны иметь возможность дуализировать закон дистрибутивности для функтора, который является одновременно и :

      first biasing . orwell = codistribR . bimap orwell orwell . biasing

codistribR :: Either (Either a c) (Either b c) -> Either (Either a b) c
codistribR = \case
    Left (Left a) -> Left (Left a)
    Left (Right c) -> Right c
    Right (Left b) -> Left (Right b)
    Right (Right c) -> Right c

Принятие этого закона (и/или аналогичного закона левой дистрибутивности) запретило бы (и, соответственно, ) изменять форму. Это потому, что по законам тождества ,orwellне может менять формы, что означает, в частности:

      first biasing (orwell (Right <$> u)) = Right u

Тогда применение распределительного закона приводит к:

      codistribR (bimap orwell orwell (biasing (Right <$> u)) = Right u

Что возможно только в том случае, еслиbiasingоставляет форму нетронутой. Таким образом, закон дистрибутивности может обеспечитьbiasedпредставляет собой классификатор форм в комплекте с возможностью выбора междуfmap fstиfmap snd. То, что все это так четко организовано, подчеркивает переписку не только междуAlternative/AltиBias, но и междуApplicativeиDecisive.