Ответ 1

Эта конкретная фраза написана Джеймсом Ири из его очень интересной Краткой, неполной и в основном неверной истории языков программирования, в которой он вымышленно приписывает ее филиппу Уодлеру.

Оригинальная цитата написана Сондерсом Мак Лейном в разделе "Категории для рабочего математика", одного из основополагающих текстов теории категорий. Здесь это в контексте, который, вероятно, является лучшим местом, чтобы узнать, что именно это означает.

Но я сделаю удар. Оригинальное предложение таково:

В общем, монада в X - это просто моноид в категории эндофункторов X, с произведением ×, замененным композицией эндофункторов и единицей, установленной единичным эндофунктором.

Х здесь есть категория. Endofunctors - это функторы от категории к себе (которая обычно относится к функциональным программистам Functor, поскольку они в основном имеют дело только с одной категорией; с категорией типов - но я отступаю). Но вы можете представить себе другую категорию, которая относится к категории "эндофункторы на X". Это категория, в которой объекты являются эндофункторами, а морфизмы - естественными преобразованиями.

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

Моноид это...

• Набор, S
• Операция, •: S × S → S
• Элемент S, e: 1 → S

... удовлетворяя этим законам:

• (a • b) • c = a • (b • c) для всех a, b и c в S
• e • a = a • e = a, для всех a в S

Монада это...

• Endofunctor, T: X → X (в Haskell, конструкторе типов * -> * с экземпляром Functor)
• Естественное преобразование, μ: T × T → T, где × означает композицию функтора (μ известен в Хаскеле как join)
• Естественное преобразование, η: я → T, где я - это тождественный эндофунктор на X (η известен как return в Хаскеле)

... удовлетворяя этим законам:

• μ ∘ Tμ = μ ∘ μT
• μ ∘ Tη = μ ∘ ηT = 1 (тождественное естественное преобразование)

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

Ответ 2

моноидной

A monoid - это набор объектов и метод их объединения. Известными моноидами являются:

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

Также есть более сложные примеры.

Кроме того, каждый моноид имеет identity, который является элементом "no-op", который не имеет никакого эффекта, когда вы объединяете его с чем-то другим:

• 0 + 7 == 7 + 0 == 7
• [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
• {} union {apple} == {apple} union {} == {apple}

Наконец, моноид должен быть ассоциативным. (вы можете уменьшить длинную цепочку комбинаций в любом случае, если вы не измените объекты слева направо) Дополнение в порядке ((5 + 3) +1 == 5+ (3+ 1)), но вычитание не является ((5-3) -1!= 5- (3-1)).

Монада

Теперь рассмотрим особый тип набора и особый способ объединения объектов.

Объекты

Предположим, что ваш набор содержит объекты особого вида: функции. И эти функции имеют интересную подпись: они не переносят числа в числа или строки в строки. Вместо этого каждая функция переносит число в список чисел в двухэтапном процессе.

• Вычислить 0 или более результатов
• Объедините эти результаты с одним ответом.

Примеры:

• 1 → [1] (просто оберните ввод)
• 1 → [] (отбросить ввод, обернуть ничто в списке)
• 1 → [2] (добавьте 1 к входу и оберните результат)
• 3 → [4, 6] (добавьте 1 для ввода и умножьте ввод на 2 и оберните несколько результатов)

Объединение объектов

Кроме того, наш способ комбинирования функций является особым. Простым способом комбинирования функции является композиция: Давайте рассмотрим приведенные выше примеры и составьте каждую функцию с собой:

• 1 → [1] → [[1]] (дважды вверните ввод)
• 1 → [] → [] (отбросить вход, дважды обернуть ничто в списке)
• 1 → [2] → [UH-OH! ] (мы не можем "добавить 1" в список! ")
• 3 → [4, 6] → [UH-OH! ] (мы не можем добавить 1 список!)

Не вдаваясь в теорию типов, дело в том, что вы можете комбинировать два целых числа, чтобы получить целое число, но вы не всегда можете составлять две функции и получать функцию одного типа. (Функции с типом a → a будут составлять, но a- > [a] не будет.)

Итак, давайте определим другой способ комбинирования функций. Когда мы объединяем две из этих функций, мы не хотим "двойного обертывания" результатов.

Вот что мы делаем. Когда мы хотим объединить две функции F и G, мы следуем этому процессу (называемому связыванием):

• Вычислить "результаты" из F, но не комбинировать их.
• Вычислить результаты применения G к каждому из результатов F отдельно, что дает коллекцию результатов.
• Сгладьте 2-уровневую коллекцию и объедините все результаты.

Вернемся к нашим примерам, позвольте комбинировать (связывать) функцию с самим собой, используя этот новый способ "привязки" функций:

• 1 → [1] → [1] (оберните ввод дважды)
• 1 → [] → [] (отбросить вход, дважды обернуть ничто в списке)
• 1 → [2] → [3] (добавьте 1, затем снова добавьте 1 и заверните результат.)
• 3 → [4,6] → [5,8,7,12] (добавьте 1 для ввода, а также умножьте ввод на 2, сохранив оба результата, затем сделайте все это снова для обоих результатов, а затем завершите окончательные результаты в списке.)

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

Связывая все вместе,

• Монада - это структура, которая определяет способ комбинирования (результатов) функций,
• аналогично тому, как моноид - это структура, которая определяет способ объединения объектов,
• где метод объединения ассоциативен,
• и там, где есть специальный "No-op", который можно комбинировать с чем-то, чтобы что-то не изменилось.

Примечания

Существует множество способов "обернуть" результаты. Вы можете сделать список или набор или отбросить все, кроме первого результата, отметив, что если результатов нет, присоедините состояние коляски, распечатайте сообщение журнала и т.д. И т.д.

Я немного поиграл с определениями в надежде получить интуитивную идею.

Я немного упростил ситуацию, настаивая на том, что наша монада работает над функциями типа a → [a]. На самом деле, монады работают над функциями типа a → m b, но обобщение - это некая техническая деталь, которая не является основным прозрением.

Ответ 3

Во-первых, расширения и библиотеки, которые мы собираемся использовать:

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

Из них RankNTypes является единственным, что абсолютно необходимо для нижеследующего. Я как-то написал объяснение RankNTypes, что некоторые люди, похоже, нашли полезные, поэтому я буду называть это.

Цитата Том Крокетт отличный ответ, у нас есть:

Монада...

• Антенна, T: X → X
• Естественное преобразование μ: T × T → T, где × означает функторную композицию
• Естественное преобразование, η: я → T, где я - тождественный контур на X

... удовлетворяющих этим законам:

• μ (μ (T × T) × T)) = μ (T × μ (T × T))
• μ (η (T)) = T = μ (T (η))

Как мы переводим это на код Haskell? Ну, начнем с понятия естественного преобразования:

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g =
    Natural { eta :: forall x. f x -> g x }

Тип формы f :-> g аналогичен типу функции, но вместо того, чтобы думать о нем как о функции между двумя типами (вида *), подумайте об этом как о морфизме между двумя функторами (каждый из видов * -> *). Примеры:

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

В принципе, в Haskell естественные преобразования являются функциями от некоторого типа f x к другому типу g x, так что переменная типа x "недоступна" вызывающему. Так, например, sort :: Ord a => [a] -> [a] нельзя превратить в естественное преобразование, потому что оно "разборчиво", какие типы мы можем создать для a. Один интуитивный способ, который я часто использую, чтобы думать об этом, следующий:

• Функтор - это способ работы над содержимым чего-то, не касаясь структуры.
• Естественное преобразование - это способ работы над структурой чего-то, не касаясь или не смотря на содержимое.

Теперь, с учетом этого, давайте рассмотрим положения определения.

Первое предложение - это "endofunctor, T: X → X". Ну, каждый Functor в Haskell является endofunctor в том, что люди называют "категорией Хаска", чьи объекты являются типами Haskell (вида *) и морфизмами которых являются функции Haskell. Это звучит как сложное утверждение, но на самом деле оно очень тривиальное. Все это означает, что a Functor f :: * -> * дает вам способ построения типа f a :: * для любого a :: * и функции fmap f :: f a -> f b из любого f :: a -> b и что они подчиняются законам функтора.

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

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

Таким образом, естественное преобразование η: я → T из определения Тома Крокетта может быть записано таким образом для любого экземпляра Monad t:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

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

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

Таким образом, естественное преобразование μ: T × T → T из определения Тома Крокетта может быть записано следующим образом:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

Утверждение о том, что это моноид в категории endofunctors, означает, что Compose (частично применяется только к его первым двум параметрам) ассоциативно и что Identity является его тождественным элементом. I., что выполнены следующие изоморфизмы:

• Compose f (Compose g h) ~= Compose (Compose f g) h
• Compose f Identity ~= f
• Compose Identity g ~= g

Это очень легко доказать, поскольку Compose и Identity определены как newtype, а отчеты Haskell Report определяют семантику newtype как изоморфизм между определяемым типом и типом аргумента к конструктору данных newtype. Так, например, пусть докажите Compose f Identity ~= f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.

Ответ 4

Примечание: Нет, это не так. В какой-то момент был комментарий к этому ответу от самого Дэн Пипони, который сказал, что причина и следствие здесь были совершенно противоположными, что он написал свою статью в ответ на ответ Джеймса Ири. Но, похоже, он был удален, возможно, с помощью какого-то компульсивного tidier.

Ниже мой первоначальный ответ.

Вполне возможно, что Ири прочитал "От моноидов до монад" , сообщение, в котором Дэн Пипони (sigfpe) выводит монады из моноидов в Haskell, с большим обсуждением теории категорий и явным упоминанием "категории endofunctors на Hask". В любом случае, любой, кто задается вопросом о том, что означает монада как моноид в категории эндофенторов, может извлечь пользу из чтения этого вывода.

Ответ 5

Я пришел к этому посту, чтобы лучше понять вывод печально известной цитаты из теории категорий Мак Лэйна для рабочего математика.

При описании того, что является чем-то, часто одинаково полезно описать, что это не так.

Тот факт, что Mac Lane использует описание для описания монады, можно предположить, что она описывает нечто уникальное для монад. Потерпите меня. Чтобы развить более широкое понимание этого утверждения, я считаю, что необходимо четко указать, что он не описывает нечто уникальное для монад; утверждение одинаково описывает Аппликатив и Стрелки среди других. По той же причине у нас может быть два моноида на Int (Sum и Product), у нас может быть несколько моноидов на X в категории эндофункторов. Но есть еще больше общих черт.

И Monad, и Applicative соответствуют критериям:

• endo => любая стрелка или морфизм, который начинается и заканчивается в одном и том же месте
• functor => любая стрелка или морфизм между двумя категориями

  (например, в повседневном Tree a → List b, но в Tree → List категорий Tree → List)

• моноид => один объект; т.е. один тип, но в этом контексте только в отношении внешнего уровня; поэтому у нас не может быть Tree → List, только List → List.

В операторе используется "Категория..." Это определяет область действия оператора. В качестве примера Категория Functor описывает область действия f * → g *, т. Any functor → Any functor, например, Tree * → List * или Tree * → Tree *.

То, что не указано в категориальном утверждении, описывает, где все разрешено.

В этом случае внутри функторов не указывается * → * aka a → b, что означает Anything → Anything including Anything else. Когда мое воображение переходит к Int → String, оно также включает в себя Integer → Maybe Int или даже Maybe Double → Either String Int где a :: Maybe Double; b :: Either String Int a :: Maybe Double; b :: Either String Int.

Таким образом, утверждение сводится к следующему:

• Область действия функтора :: fa → gb (т.е. любой параметризованный тип для любого параметризованного типа)
• endo + functor :: fa → fb (т.е. любой один параметризованный тип к одному и тому же параметризованному типу)... по-другому,
• моноид в категории эндофунктор

Итак, где же сила этой конструкции? Чтобы оценить всю динамику, мне нужно было увидеть, что типичные рисунки моноида (одиночный объект с чем-то вроде стрелки идентичности, :: single object → single object) не иллюстрируют, что мне разрешено использовать стрелку параметризован любым количеством моноидных значений из объекта одного типа, разрешенного в моноиде. Определение эквивалентности стрелкой endo ~ identity игнорирует значение типа функтора, а также тип и значение самого внутреннего слоя "полезной нагрузки". Таким образом, эквивалентность возвращает true в любой ситуации, когда совпадают функторные типы (например, Nothing → Just * → Nothing эквивалентно Just * → Just * → Just * поскольку они оба Maybe → Maybe → Maybe).

Боковая панель: ~ снаружи является концептуальным, но это самый левый символ в fa. Он также описывает, что "Хаскелл" читает первым (большая картинка); так что тип "снаружи" по отношению к значению типа. Взаимосвязь между слоями (цепочкой ссылок) в программировании нелегко установить в категории. Категория набора используется для описания типов (Int, Strings, Maybe Int и т.д.), Которые включают в себя категорию функторов (параметризованные типы). Цепочка ссылок: тип функтора, значения функтора (элементы этого набора функторов, например, Nothing, Just) и, в свою очередь, все остальное, на которое указывает каждое значение функтора. В категории отношение описывается по-другому, например, return :: a → ma считается естественным преобразованием из одного функтора в другой, в отличие от всего, что упоминалось ранее.

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

• снаружи он выглядит как один объект (например, :: List); статический
• но внутри, допускает много динамики
  • любое количество значений того же типа (например, Empty | ~ NonEmpty), что и fodder для функций любой арности. Тензорный продукт уменьшит любое количество входов до единого значения... для внешнего слоя (~ fold которая ничего не говорит о полезной нагрузке)
  • бесконечный диапазон как типа, так и значений для самого внутреннего слоя

В Haskell важно уточнить применимость этого утверждения. Мощь и универсальность этой конструкции не имеет абсолютно никакого отношения к монаде как таковой. Другими словами, конструкция не полагается на то, что делает монаду уникальной.

При попытке выяснить, следует ли создавать код с общим контекстом для поддержки вычислений, которые зависят друг от друга, по сравнению с вычислениями, которые могут выполняться параллельно, это позорное утверждение, как бы оно ни описывалось, не является контрастом между выбором Аппликатив, Стрелы и Монады, а точнее это описание того, насколько они одинаковы. Для данного решения утверждение является спорным.

Это часто неправильно понимают. Утверждение продолжает описывать join :: m (ma) → ma как тензорное произведение для моноидального эндофунктора. Однако в нем не сформулировано, как в контексте этого утверждения (<*>) также можно было бы выбрать. Это действительно пример шести/полдюжины. Логика объединения значений абсолютно одинакова; один и тот же вход генерирует одинаковый выход из каждого (в отличие от моноидов Sum и Product для Int, потому что они генерируют разные результаты при объединении Ints).

Итак, резюмируем: моноид в категории эндофункторов описывает:

   ~t :: m * -> m * -> m *
   and a neutral value for m *

(<*>) и (>>=) оба обеспечивают одновременный доступ к двум значениям m для вычисления единственного возвращаемого значения. Логика, используемая для вычисления возвращаемого значения, точно такая же. Если бы не было различных форм функций, они параметризуются (f :: a → b сравнению с k :: a → mb) и позицией параметра с тем же типом возвращаемого результата вычисления (т.е. A a → b → b против b → a → b для каждого соответственно), я подозреваю, что мы могли бы параметризовать моноидальную логику, тензорное произведение, для повторного использования в обоих определениях. В качестве упражнения, чтобы понять суть, попробуйте и реализуйте ~t, и вы получите (<*>) и (>>=) зависимости от того, как вы решите определить его, например, forall ab.

Если моя последняя точка концептуально верна как минимум, тогда она объясняет точное и единственное вычислительное различие между Applicative и Monad: функции, которые они параметризуют. Другими словами, различие является внешним по отношению к реализации этих классов типов.

В заключение, по моему собственному опыту, печально известная цитата из Mac Lane предоставила отличный мем "goto", ориентир для меня, на который я могу ссылаться при навигации по Category, чтобы лучше понять идиомы, используемые в Haskell. Ему удается захватить всю мощь мощных вычислительных возможностей, которые чудесно доступны в Haskell.

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

- E

Ответ 6

Ответы здесь отлично справляются с определением моноидов и монад, однако они все еще не отвечают на вопрос:

И на менее важной ноте, это правда, и если да, то могли бы вы дать объяснение (надеюсь, что это может понять кто-то, кто не имеет большого опыта Хаскелла)?

Суть вопроса, который здесь отсутствует, - это другое понятие "моноид", точнее, так называемая категоризация - понятие "моноид" в моноидальной категории. К сожалению, сама книга Mac Lane делает ее очень запутанной:

В общем, монада в X - это просто моноид в категории эндофункторов в X, с продуктом ×, замененным композицией эндофункторов и единицей, установленной единичным эндофунктором.

Основная путаница

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

Тем не менее, это не правильное толкование, которое книга не может прояснить на этом этапе. Монада f является фиксированным эндофунктором, а не подмножеством эндофункторов, замкнутых по композиции. Обычной конструкцией является использование f для генерации моноида путем взятия набора всех композиций k -fold f^k = f(f(...)) из f, включая k=0, который соответствует идентификатору f^0 = id. И теперь набор S всех этих степеней для всех k>=0 действительно является моноидом "с произведением ×, замененным композицией эндофункторов, и единицей, установленной единичным эндофунктором".

И еще:

• Этот моноид S можно определить для любого функтора f или даже буквально для любой собственной карты X. Это моноид, сгенерированный f.
• Моноидальная структура S, заданная композицией функторов и тождественным функтором, не имеет ничего общего с тем, является ли f монадой или нет.

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

(Строгие) моноидальные категории

Переходя к главе VII о моноидах (которая выходит позже главы VI о монадах), мы находим определение так называемой строгой моноидальной категории как тройной (B, *, e), где B - категория, *: B x B-> B бифунктор (функтор по отношению к каждому компоненту с фиксированным другим компонентом), а e - это единичный объект в B, удовлетворяющий законам ассоциативности и единиц:

(a * b) * c = a * (b * c)
a * e = e * a = a

для любых объектов a,b,c из B и одинаковых идентификаторов для любых морфизмов a,b,c с заменой e на id_e, тождественный морфизм e. Теперь полезно отметить, что в нашем интересном случае, где B является категорией эндофункторов в X с естественными преобразованиями в качестве морфизмов, * композицией функторов и e функтором тождества, все эти законы удовлетворены, что может быть подтверждено напрямую.

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

Моноиды в моноидальных категориях

Наконец, в разделе 3 "Моноиды" главы VII дается фактическое определение:

Моноид c в категории моноидов (B, *, e) является объектом B с двумя стрелками (морфизмы)

mu: c * c -> c
nu: e -> c

сделать 3 диаграммы коммутативными. Напомним, что в нашем случае это морфизмы в категории эндофункторов, которые являются естественными преобразованиями, точно соответствующими join и return для монады. Связь становится еще более ясной, когда мы делаем композицию * более явной, заменяя c * c на c^2, где c - наша монада.

Наконец, обратите внимание, что 3 коммутативные диаграммы (в определении моноида в моноидальной категории) написаны для общих (нестрогих) моноидальных категорий, в то время как в нашем случае все естественные преобразования, возникающие как часть моноидальной категории, на самом деле являются тождествами. Это сделает диаграммы точно такими же, как в определении монады, и соответствие будет полным.

Заключение

Таким образом, любая монада по определению является эндофунктором, следовательно, объектом в категории эндофункторов, где монадические операторы join и return удовлетворяют определению моноида в этой конкретной (строгой) моноидальной категории. Наоборот, любой моноид в моноидальной категории эндофункторов по определению является тройным (c, mu, nu), состоящим из объекта и двух стрелок, например, естественные преобразования в нашем случае, удовлетворяющие тем же законам, что и монада.

Наконец, обратите внимание на ключевое различие между (классическими) моноидами и более общими моноидами в моноидальных категориях. Две стрелки mu и nu выше больше не являются бинарной операцией и единицей в наборе. Вместо этого у вас есть один фиксированный endofunctor c. Композиция функторов * и один только функтор идентичности не обеспечивают полной структуры, необходимой для монады, несмотря на это запутанное замечание в книге.

Другой подход заключается в сравнении со стандартным моноидом C всех собственных карт набора A, где бинарная операция представляет собой композицию, которую можно увидеть для отображения стандартного декартового произведения C x C в C, Переходя к категоризированному моноиду, мы заменяем декартово произведение x на функторную композицию *, и двоичная операция заменяется естественным преобразованием mu из c * c - c, то есть набор операторов join

join: c(c(T))->c(T)

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

return: T->c(T) 

Но теперь больше нет декартовых произведений, поэтому нет пар элементов и, следовательно, нет бинарных операций.