Монады как дополнения

Ответ 1

Изменить: просто для удовольствия, я сделаю это правильно. Исходный ответ сохранен ниже

Текущий код присоединения для дополнительных категорий теперь находится в пакете дополнений: http://hackage.haskell.org/package/adjunctions

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

Примыкание f (D → C) и g (C → D), записанное f - | г, можно охарактеризовать несколькими способами. Мы будем использовать описание concit/unit (epsilon/eta), которое дает два естественных преобразования (морфизмы между функторами).

class (Functor f, Functor g) => Adjoint f g where
     counit :: f (g a) -> a
     unit   :: a -> g (f a)

Заметим, что "a" в конситуации действительно является тождественным функтором в C, а "a" в единице действительно является тождественным функтором в D.

Мы также можем восстановить определение присоединения гомосекретаря из определения контингента/единицы.

phiLeft :: Adjoint f g => (f a -> b) -> (a -> g b)
phiLeft f = fmap f . unit

phiRight :: Adjoint f g => (a -> g b) -> (f a -> b)
phiRight f = counit . fmap f

В любом случае теперь мы можем определить Monad из нашего приложения unit/concit так:

instance Adjoint f g => Monad (Compose g f) where
    return x = Compose $ unit x
    x >>= f  = Compose . fmap counit . getCompose $ fmap (getCompose . f) x

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

instance Adjoint ((,) a) ((->) a) where
    -- counit :: (a,a -> b) -> b
    counit (x, f) = f x
    -- unit :: b -> (a -> (a,b))
    unit x = \y -> (y, x)

И теперь синоним типа

type State s = Compose ((->) s) ((,) s)

И если мы загрузим это в ghci, мы можем подтвердить, что государство - это наша классическая государственная монада. Обратите внимание, что мы можем взять противоположную композицию и получить Costant Comonad (ака магазин comonad).

Есть несколько других дополнений, которые мы можем сделать в монады таким образом (например, пара (Bool,)), но это своего рода странные монады. К сожалению, мы не можем делать дополнения, которые побуждают Reader и Writer непосредственно в Haskell приятным образом. Мы можем делать Cont, но, как описывает copumpkin, для этого требуется присоединение от противоположной категории, поэтому на самом деле она использует другую "форму" класса "Adjoint", которая меняет некоторые стрелки. Эта форма также реализована в другом модуле в пакете дополнений.

этот материал рассматривается по-разному в статье Дерека Элкинса в книге "Монад-ридер 13" - "Расчетные монады с теорией категорий: http://www.haskell.org/wikiupload/8/85/TMR-Issue13.pdf

Кроме того, недавно обновленная статья Kan Extensions for Program Optimization Hinze просматривает построение монады списка из привязки между Mon и Set: http://www.cs.ox.ac.uk/ralf.hinze/Kan.pdf

Старый ответ:

Две ссылки.

1) Категория-дополнения предоставляют, как всегда, представление о дополнениях и о том, как из них возникают монады. Как обычно, хорошо подумать, но довольно легко документировать: http://hackage.haskell.org/packages/archive/category-extras/0.53.5/doc/html/Control-Functor-Adjunction.html

2) -Cafe также поставляет с многообещающим, но кратким обсуждением роли присоединения. Некоторые из них могут помочь в интерпретации категорий-дополнений: http://www.haskell.org/pipermail/haskell-cafe/2007-December/036328.html

Ответ 2

Дерек Элкинс недавно показывал мне поужинать, как Cont Monad возникает из-за составления контравариантного функтора (_ -> k) с самим собой, поскольку он, оказывается, является самосопряженным. То, как вы получите (a -> k) -> k. Однако его контингент приводит к устранению двойного отрицания, которое невозможно записать в Haskell.

Для некоторого кода Agda, который иллюстрирует и доказывает это, см. http://hpaste.org/68257.

Ответ 3

Это старый поток, но я нашел интересный вопрос, поэтому я сам сделал некоторые расчеты. Надеюсь, Бартош все еще там и может прочитать это.

Действительно, конструкция Эйленберга-Мура дает в этом случае очень четкую картину. (Я буду использовать обозначение CWM с синтаксисом Haskell)

Пусть T будет монадой списка < T,eta,mu > (eta = return и mu = concat) и рассмотрим Т-алгебру h:T a -> a.

(Заметим, что T a = [a] - свободный моноид <[a],[],(++)>, то есть тождество [] и умножение (++).)

По определению h должен удовлетворять h.T h == h.mu a и h.eta a== id.

Теперь, некоторая простая диаграммная гонка доказывает, что h фактически индуцирует моноидную структуру на a (определяемую x*y = h[x,y]), и что h становится моноидным гомоморфизмом для этой структуры.

Наоборот, любая моноидная структура < a,a0,* >, определенная в Haskell, естественно определяется как T-алгебра.

Таким образом (h = foldr ( * ) a0, функция, которая "заменяет" (:) на (*) и отображает [] в a0, тождество).

Таким образом, в этом случае категория T-алгебр является только категорией моноидных структур, определяемых в Haskell, HaskMon.

(Пожалуйста, проверьте, что морфизмы в T-алгебрах являются фактически моноидными гомоморфизмами.)

Он также характеризует списки как универсальные объекты в HaskMon, так же как свободные произведения в Grp, полиномиальные кольца в CRng и т.д.

Примыкание, соответствующее указанной конструкции, < F,G,eta,epsilon >

где

• F:Hask -> HaskMon, который берет тип a в "свободный моноид, порожденный a", то есть [a],
• G:HaskMon -> Hask, забывчивый функтор (забудьте умножение),
• eta:1 -> GF, естественное преобразование, определяемое \x::a -> [x],
• epsilon: FG -> 1, естественное преобразование, определяемое функцией складывания выше               ( "каноническая сюръекция" от свободного моноида к его частному моноиду)

Далее, есть еще одна "категория Клейсли" и соответствующее ее присоединение. Вы можете проверить, что это только категория типов Haskell с морфизмами a -> T b, где его композиции даны так называемой "композицией Клейсли" (>=>). Типичный программист Haskell найдет эту категорию более знакомой.

Наконец, как показано в CWM, категория T-алгебр (соответственно категории Клейсли) становится терминальным (соответственно начальным) объектом в категории предложений, которые определяют список монады T в подходящем смысле.

Я предлагаю выполнить аналогичные вычисления для функтора двоичного дерева T a = L a | B (T a) (T a), чтобы проверить ваше понимание.

Ответ 4

Я нашел стандартную конструкцию вспомогательных функторов для любой монады Эйленберга-Мура, но я не уверен, добавляет ли она какую-либо информацию о проблеме. Вторая категория в конструкции - категория Т-алгебр. Алгебра T добавляет "продукт" к начальной категории.

Так как это будет работать для монады списка? Функтор в монаде списка состоит из конструктора типа, например, Int->[Int] и отображения функций (например, стандартного применения карты к спискам). Алгебра добавляет отображение из списков в элементы. Одним из примеров было бы добавление (или умножение) всех элементов списка целых чисел. Функтор F принимает любой тип, например Int, и отображает его в алгебру, определенную в списках Int, где произведение определяется монадическим соединением (или наоборот, объединение определяется как произведение). Забывающий функтор G берет алгебру и забывает произведение. Пара F, G, сопряженных функторов затем используется для построения монады обычным образом.

Я должен сказать, что я не мудрее.

Ответ 5

Если вас это интересует, вот некоторые мысли о неспециалисте о роли монадов и адъюнкций в языках программирования:

Прежде всего, для данной монады T существует единственное присоединение к категории Клейсли T. В Haskell использование монадов в основном ограничивается операциями в этой категории  (которая по существу является категорией свободных алгебр, не имеет отношения). Фактически, все, что можно сделать с Монахом Хаскелла, состоит в том, чтобы составить некоторые морфизмы Клейсли введите a->T b с помощью выражений do, (>>=) и т.д., чтобы создать новый морфизм. В этом контексте роль монадов ограничивается только экономикой нотации. Одна из них использует ассоциативность морфизмов, чтобы иметь возможность писать (скажем) [0,1,2] вместо (Cons 0 (Cons 1 (Cons 2 Nil))), то есть вы можете записать последовательность как последовательность, а не как дерево.

Даже использование IO-монад не является существенным, поскольку текущая система типа Haskell является мощной достаточно для реализации инкапсуляции данных (экзистенциальные типы).

Это мой ответ на ваш первоначальный вопрос, но мне любопытно, что эксперты Haskell должны сказать об этом.

С другой стороны, как мы уже отмечали, существует также 1-1 соответствие между монадами и (T-) -алгебр. Согласование, в терминах MacLane, является "способом для выражения эквивалентности категорий ". В типичной установке дополнений <F,G>:X->A, где F "генератора свободных алгебр" и G - "забывчивый функтор", соответствующая монада будет (с помощью T-алгебр) описать, как (и когда) построена алгебраическая структура A на объектах X.

В случае Hask и монады списка T структура, которая T вводит, заключается в том, что моноида, и это может помочь нам установить свойства (включая правильность) кода через алгебраические методов, которые обеспечивает теория моноидов. Например, функция foldr (*) e::[a]->a может легко можно рассматривать как ассоциативную операцию, если <a,(*),e> является моноидом, факт, который может быть использован компилятором для оптимизации вычисления (например, parallelism). Другое приложение - идентифицировать и классифицировать "рекурсионные шаблоны" в функциональном программировании с использованием категориальных методы в надежде (частично) избавиться от "goto функционального программирования", Y (произвольный рекурсионный комбинатор).

По-видимому, такие приложения являются одной из основных мотивов создателей Теории категорий (MacLane, Eilenberg и т.д.), а именно, установить естественную эквивалентность категорий и перенести известный метод в одну категорию к другому (например, гомологические методы к топологическим пространствам, алгебраические методы программирования и т.д.). Здесь сопряжения и монады являются незаменимыми инструментами для использования этого соединения категорий. (Кстати, понятие монадов (и его двойственных, comonads) настолько общее, что можно даже зайти так далеко, чтобы определить "когомологии" Haskell. Но я еще не подумал.)

Что касается неопределенных функций, о которых вы упомянули, мне гораздо меньше сказать... Но обратите внимание, что; если присоединение <F,G>:Hask->A для некоторой категории A определяет список monad T, должен существовать уникальный "функтор сравнения" K:A->MonHask (категория моноидов, определяемых в Haskell), см. CWM. Фактически это означает, что ваша категория интересов должна быть категорией моноидов в некоторой ограниченной форме (например, для ее отсутствия может отсутствовать некоторые частные, но не свободные алгебры).

Наконец, некоторые замечания:

Функтор двоичного дерева, упомянутый в моей последней публикации, легко обобщает на произвольный тип данных T a1 .. an = T1 T11 .. T1m | .... А именно, любой тип данных в Haskell естественно определяет монаду (вместе с соответствующей категорией алгебр и категорией Клейсли), что является результатом того, что любой конструктор данных в Haskell является полным. Это еще одна причина, почему я считаю класс Haskell Monad не намного больше, чем синтаксический сахар (что, конечно, довольно важно на практике).