Монада - это просто моноид в категории эндофункторов, в чем проблема?

Question

Кто первым сказал следующее?

Монада - это просто моноид в категория эндофункторов, что такое проблема?

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Монада ...

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

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

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

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

Answer 2

Интуитивно, я думаю, что сказочный математический словарь говорит о том, что:

Monoid

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

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

Есть и более сложные примеры.

Далее, каждый моноид имеет идентификатор , то есть тот элемент "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)).

Монада

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

Предметы

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

1. Вычислить 0 или более результатов
2. Объедините эти результаты в один ответ как-нибудь.

Примеры:

• 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, мы следуем этому процессу (называемому binding ):

1. Вычислить «результаты» из F, но не объединять их.
2. Вычислите результаты применения G к каждому из результатов F по отдельности, получая набор результатов.
3. Свести 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 , но обобщение является своего рода технической деталью, которая не является основным понятием.

Answer 3

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

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

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

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

Монада ...

• Эндофунктор, T: X -> X
• Естественное преобразование, μ: T × T -> T , где × означает функторную композицию
• Естественное преобразование, η: I -> T , где I - идентификационный эндофунктор на 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 является эндофунктором в том, что люди называют «категорией Hask», чьи объекты являются типами Haskell (типа *) и чьи морфизмы являются функциями Haskell.Это звучит как сложное утверждение, но на самом деле оно очень тривиально.Все это означает, что 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)

Итак, естественное преобразование η: I -> 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's 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)

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

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

Это оченьлегко доказать, потому что Compose и Identity определены как newtype, а отчеты Haskell определяют семантику 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.

Answer 4

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

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

---

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

Answer 5

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

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

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

И Монада, и Аппликатив соответствуют критериям:

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

  (например, изо дня в день Tree a -> List b, но в категории 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.

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

• область действия функтора :: f a -> g b (т. Е. Любой параметризованный тип для любого параметризованного типа)
• endo + functor :: f a -> f b (т. Е. Любой один параметризованный тип к одному и тому же параметризованному типу) ... иначе говоря,
• моноид в категории эндофунктор

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

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

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

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

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

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

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

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

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

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

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

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

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

- E