Сочетание государственной монады с косатской комонадой

Question

Как совместить государственную монаду S -> (A, S) с косатой (E->A, E)?

Я пробовал обе очевидные комбинации S -> ((E->A, E), S) а также (E->S->(A, S), E) но тогда в любом случае я не знаю, как определить операции (return, extract... и т. д.) для комбинации.

Answer 1

Объединение двух монад O а также I дает монаду, если либо O или же I это означает, что есть extract метод. Каждая комонада совмещена. Если оба O и я соединился, тогда у вас есть два разных "естественных" способа получить монаду, которые предположительно не эквивалентны.

У тебя есть:

unit_O :: a -> O a
join_O :: O (O a) -> O a
unit_I :: a -> I a
join_I :: I (I a) -> I a

Здесь я добавил _O а также _I суффикс для ясности; в реальном коде на Haskell их там не будет, так как средство проверки типов вычисляет это самостоятельно.

Ваша цель - показать, что O (I O (I a))) это монада Давайте предположим, что O это означает, что есть функция extract_O :: O a -> a,

Тогда мы имеем:

unit :: a -> O (I a)
unit = unit_O . unit_I
join :: O (I (O (I a))) -> O (I a)

Проблема, конечно, заключается в реализации join, Мы придерживаемся этой стратегии:

• fmap по внешнему O
• использование extract_O прокатиться изнутри O
• использование join_I объединить два I монады

Это приводит нас к

join = fmap_O $ join_I . fmap_I extract

Чтобы сделать это, вам также нужно определить

newtype MCompose O I a = MCompose O (I a)

и добавьте соответствующие конструкторы типов и деконструкторы в определения выше.

Другое альтернативное использование extract_I вместо extract_O, Эта версия еще проще:

join = join_O . fmap_O extract_I

Это определяет новую монаду. Я предполагаю, что вы можете определить новую комонаду таким же образом, но я не пытался это сделать.

Answer 2

Как показывает другой ответ, обе комбинации S -> ((E->A, E), S) а также (E->S->(A, S), E)иметь экземпляры Monad и Comonad одновременно. Фактически предоставление экземпляра Monad/Comonad эквивалентно предоставлению моноидной структуры соотв. его точки ∀rr->f(r) или его точки intsrf(r)->r, по крайней мере, в классическом неконструктивном смысле (я не знаю конструктивного ответа). Этот факт говорит о том, что на самом деле Functor f имеет очень хорошие шансы, что он может быть как Monad, так и Comonad, при условии, что его точки и копоинты нетривиальны.

Однако реальный вопрос заключается в том, имеют ли экземпляры Monad/Comonad, построенные как таковые, естественные вычислительные / категориальные значения. В этом конкретном случае я бы сказал "нет", потому что у вас, кажется, нетаприорных знаний о том, как составлять их так, чтобы они соответствовали вашим вычислительным потребностям.

Стандартный категориальный способ составления двух (со) монад - через приставки. Позвольте мне обобщить вашу ситуацию:

      Fₑ         Fₛ
      -->       -->
Hask  ⊣   Hask  ⊣ Hask
      <--       <--
      Gₑ         Gₛ

Fₜ(a) = (a,t)
Gₜ(a) = (t->a)

Доказательство Fₜ ⊣ Gₜ:

Fₜ(x) -> y   ≃
(x,t) -> y   ≃
x  -> (t->y) ≃
x  -> Gₜ(y)

Теперь вы можете видеть, что монада состояния (s->(a,s)) ≃ (s->a,s->s) является композицией GₛFₛ, а косатная комонада - FₑGₑ. Это присоединение говорит о том, что Hask можно интерпретировать как модель (со) состояния (со) алгебр.

Теперь "дополнения составляют". Например,

FₛFₑ(x) -> y ≃
Fₑ(x)   -> Gₛ(y) ≃
x       -> GₑGₛ(y)

Так что FₛFₑ ⊣ GₑGₛ. Это дает пару монад и комонад, а именно

T(a) = GₑGₛFₛFₑ(a)
     = GₑGₛFₛ(a,e)
     = GₑGₛ(a,e,s)
     = Gₑ(s->(a,e,s))
     = e->s->(a,e,s)
     = ((e,s)->a, (e,s)->(e,s))

G(a) = FₛFₑGₑGₛ(a)
     = FₛFₑGₑ(s->a)
     = FₛFₑ(e->s->a)
     = Fₛ(e->s->a,e)
     = (e->s->a,e,s)
     = ((e,s)->a, (e,s))

T - это просто монада состояний с состоянием (e, s), G - это коматада состояний с косатой (e, s), так что они имеют очень естественные значения.

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

С другой стороны, непосредственное составление монад / комонад кажется очень редкой практикой в ​​математике. Это потому, что часто (со) монаду считают носителем (со) алгебраической теории, а не моделью. В этой интерпретации соответствующие дополнения являются моделями, а не монадой. Проблема в том, что для составления двух теорий требуется другая теория, теория о том, как их составлять. Например, представьте, что вы сочиняете две теории моноидов. Тогда вы можете получить как минимум две новые теории, а именно теорию списков списков, или кольцевые алгебры, где распределяются два вида бинарных операций. Ни один не является априори лучше / более естественным, чем другой. Это значение "монады не сочиняют"; он не говорит, что композиция не может быть монадой, но он говорит, что вам понадобится другая теория, как их составить.

Напротив, составление дополнений естественным образом приводит к другому присоединению просто потому, что, делая это, вы безразлично определяете правила составления двух данных теорий. Таким образом, взяв монаду составного присоединения, вы получите теорию, которая также определяет правила композиции.