Теория Монады и Хаскелл

Ответ 1

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

Кто-нибудь знает учебник, который начинается с теории категорий и объясняет IO, состояние, список монадов в этих терминах?

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

Функтор обычно отображается с типом: (a → b) → (m a → m b). Я включил вторую скобку, чтобы подчеркнуть симметрию.

Но это endofunctor, поэтому домен и кодомен не должны быть такими же?:

Я подозреваю, что вы неверно истолковываете, как переменные типа в Haskell относятся к концепциям теории категорий.

Прежде всего, да, это указывает на endofunctor, в категории типов Haskell. Однако переменная типа, такая как a, не является чем-то в этой категории; это переменная, которая (неявно) универсально квантуется по всем объектам в категории. Таким образом, тип (a -> b) -> (a -> b) описывает только endofunctors, которые отображают каждый объект для себя.

Конструкторы типов описывают инъективную функцию для объектов, где элементы конструктора codomain не могут быть описаны никакими средствами, кроме как применение конструктора типа. Даже если два типа конструкторов производят изоморфные результаты, результирующие типы остаются различными. Обратите внимание, что конструкторы типов в общем случае не являются функторами.

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

Затем результирующая функция говорит, что для любого конструктора типов m, который имеет fmap, определенный для любых двух объектов a и b и морфизма между ними, мы можем найти морфизм между типами заданные приложением m to a и b.

Обратите внимание, что хотя вышеописанное, конечно, определяет endofunctor на Hask, оно даже не достаточно отдаленно достаточно для описания всех таких endofunctors.

Но фактические естественные преобразования, которые мы используем, имеют тип:

a → m a

m a → (a → m b) → m b

Являются ли эти подмножества общего вида выше? и почему они являются естественными преобразованиями?

Ну, нет, это не так. Естественное преобразование является примерно функцией (не функтором) между функторами. Два естественных преобразования, которые определяют монаду М, выглядят как I -> M, где я - тождественный функтор, а M ∘ M -> M где ∘ - функторная композиция. В Haskell у нас нет хорошего способа работать непосредственно с истинным функтором идентичности или с составом функтора. Вместо этого мы отбрасываем функтор тождества, чтобы получить только (Functor m) => a -> m a для первого и выписать приложение-конструктор вложенного типа как (Functor m) => m (m a) -> m a для второго.

Первый из них, очевидно, return; вторая - это функция, называемая join, которая не является частью класса типа. Однако join может быть записано в терминах (>>=), а последнее чаще всего полезно в повседневном программировании.

Что касается конкретных монад, то, если вы хотите получить более математическое описание, выполните быстрый набросок примера:

Для некоторого фиксированного типа S рассмотрим два функтора F и G, где F (x) = (S, x) и G (x) = S → x (Мы надеемся, очевидно, что это действительно действующие функторы).

Эти функторы также являются сопряженными; рассмотрим естественные преобразования unit :: x -> G (F x) и counit :: F (G x) -> x. Расширение определений дает нам unit :: x -> (S -> (S, x)) и counit :: (S, S -> x) -> x. Типы предполагают использование нестандартных приложений и кортежей; не стесняйтесь проверить, что они работают должным образом.

Примыкание дает монаду по составу функторов, поэтому, беря G ∘ F и расширяя определение, получаем G (F x) = S → (S, x), что является определением State монада. unit для присоединения, конечно, return; и вы можете использовать counit для определения join.

Ответ 2

Эта страница делает именно это. Я думаю, что ваша основная путаница в том, что класс действительно не делает функтор Type a, но определяет функтор из категории типов Haskell в категорию этого типа.

Следуя обозначениям ссылки, считая, что F является функтором Хаскелла, это означает, что функтор из категории Хаска относится к категории F.

Ответ 3

Грубо говоря, Haskell делает свою теорию категорий всего лишь в одной категории, объекты которой являются типами Haskell и стрелки которых являются функциями между этими типами. Это определенно не универсальный язык для моделирования теории категорий.

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

[Если вы следуете математической литературе, технически операция "(a- > b) → (ma → mb)" - это просто стрелочная часть endofunctor m, а "m" - объект часть]

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

Предположим, что у вас есть монада 'm' в категории C типов Haskell. Его категория Клейсли Kl (m) имеет те же объекты, что и C, а именно типы Хаскелла, но стрелка a (f) ~ > b в Kl (m) является стрелкой a - (f) → mb в C. (I В моей стреле Клейсли я использовал короткую линию, чтобы отличить их). Повторить: объекты и стрелки Kl (C) также являются объектами и стрелками C, но стрелки указывают на разные объекты в Kl (C), чем на C. Если это не ударит вас как нечетное, прочитайте его снова больше осторожно!

Конкретно рассмотрим монаду Maybe. Его категория Клейсли - это просто коллекция типов Хаскелла, а ее стрелки a (f) ~ > b - функции a - (f) → Возможно, b. Или рассмотрим монадию (State s), стрелки a ~ (f) ~ > b являются функциями a - (f) → (State sb) == a - (f) → (s → (s, b)), Во всяком случае, вы всегда пишете стрелку в виде короткой стрелки, как сокращение для того, чтобы что-то делать с типом кодекса ваших функций.

[Обратите внимание, что состояние не является монадой, потому что тип состояния - * → * → *, поэтому вам нужно указать один из параметров типа, чтобы превратить его в математическую монаду.]

До сих пор так хорошо, надеюсь, но предположим, что вы хотите составить стрелки a ~ (f) ~ > b и b ~ (g) ~ > c. Это действительно функции Haskell a - (f) → mb и b - (g) → mc, которые вы не можете создать, потому что типы не совпадают. Математическое решение состоит в том, чтобы использовать естественное преобразование "умножения" u: mm- > m монады следующим образом: a (f) ~ > b ~ (g) ~ > c == a - (f) → mb - (mg) → mmc - (u_c) → mc, чтобы получить стрелку a- > mc, которая является стрелкой Клейсли a (f; g) ~ > c по мере необходимости.

Возможно, конкретный пример помогает здесь. В Модификации Maybe вы не можете создавать функции f: a → Возможно, b и g: b → Может быть c напрямую, но, подняв g на

Maybe_g :: Maybe b -> Maybe (Maybe c)
Maybe_g Nothing = Nothing
Maybe_g (Just a) = Just (g a)

и используя "очевидный"

u :: Maybe (Maybe c) -> Maybe c
u Nothing = Nothing
u (Just Nothing) = Nothing
u (Just (Just c)) = Just c

вы можете сформировать композицию u . Maybe_g . f, которая является функцией a → Maybe c, которую вы хотели.

В монадии (State s) она похожа, но беспорядочна: учитывая две монадические функции a ~ (f) ~ > b и b ~ (g) ~ > c, которые действительно a - (f) → (s- > (s, b)) и b - (g) → (s → (s, c)) под капотом, вы их складываете, поднимая g в

State_s_g :: (s->(s,b)) -> (s->(s,(s->(s,c))))
State_s_g p s1 = let (s2, b) = p s1 in (s2, g b)

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

u :: (s->(s,(s->(s,c)))) -> (s->(s,c))
u p1 s1 = let (s2, p2) = p1 s1 in p2 s2

который (вроде) подключает конечное состояние f к исходному состоянию g.

В Haskell это оказывается немного неестественным способом работы, поэтому вместо него есть функция (>>=), которая в основном делает то же самое, что и u, но таким образом, что упрощает ее реализацию и использование. Это важно: (>>=) не является естественным преобразованием 'u'. Вы можете определить каждый в терминах другого, так что они эквивалентны, но это не одно и то же. Версия Haskell 'u' написана join.

Другое, отсутствующее в этом определении категорий Клейсли, является тождеством для каждого объекта: a ~ (1_a) ~ > a, который действительно a - (n_a) → ma, где n - естественное преобразование единицы. Это написано return в Haskell и, похоже, не вызывает такой путаницы.

Я изучил теорию теории, прежде чем я пришел в Haskell, и у меня также были трудности с несоответствием между тем, что математики называют монадой, и как они выглядят в Haskell. Это не проще с другого направления!

Ответ 4

Не уверен, что я понимаю, в чем вопрос, но да, вы правы, монада в Haskell определяется как тройка:

m :: * -> * -- this is endofunctor from haskell types to haskell types!
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b

но общее определение из теории категорий - это еще одна тройка:

m :: * -> *
return :: a -> m a
join ::  m (m a) -> m a

Это немного запутанно, но не так сложно показать, что эти два определения равны. Для этого нам нужно определить join в терминах (>>=) (и наоборот). Первый шаг:

join :: m (m a) -> m a
join x = ?

Это дает нам x :: m (m a).
Все, что мы можем сделать с чем-то типа m _, это aply ( → =):

(x >>=) :: (m a -> m b) -> m b

Теперь нам нужно что-то в качестве второго аргумента для ( → =), а также, от типа соединения мы имеем ограничение (x >>= y) :: ma.
Итак, y здесь будет иметь тип y :: ma -> ma и id :: a -> a подходит для него очень хорошо:

join x = x >>= id

Другой способ

(>>=) :: ma -> (a -> mb) -> m b
(>>=) x y = ?

Где x :: m a и y :: a -> m b. Чтобы получить m b из x и y, нам нужно что-то типа a.
К сожалению, мы не можем извлечь a из m a. Но мы можем заменить его на что-то еще (помните, что монада также является функтором):

fmap :: (a -> b) -> m a -> m b
fmap y x :: m (m b)

И он отлично подходит для аргумента для join: (>>=) x y = join (fmap y x).

Ответ 5

Лучший способ взглянуть на монады и вычислительные эффекты - начать с того, где Haskell получил понятие монады для вычислительных эффектов, а затем взгляните на Haskell, когда вы это поняли. См. Этот документ, в частности: Понятия вычислений и монады, Е. Могги.

См. также предыдущую статью Могги, в которой показано, как монады работают только для лямбда-исчисления: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.26.2787

Тот факт, что monads захватывает подстановку, между прочим (http://blog.sigfpe.com/2009/12/where-do-monads-come-from.html), и замена является ключом к исчислению лямбда, должен дать хорошую подсказку относительно того, почему у них так много выразительной силы.

Ответ 6

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

Ответ 7

Один из способов взглянуть на IO - рассматривать его как странную государственную монаду. Помните, что государственная монада выглядит так:

data State s a = State (s -> (s, a))

где аргумент "s" - это тип данных, который вы хотите пропустить через вычисление. Кроме того, эта версия "State" не имеет действий "get" и "put", и мы не экспортируем конструктор.

Теперь представьте себе тип

data RealWorld = RealWorld ......

Это не имеет реального определения, но, по-видимому, значение типа RealWorld содержит состояние всей вселенной вне компьютера. Конечно, мы никогда не можем иметь значение типа RealWorld, но вы можете себе представить что-то вроде:

getChar :: RealWorld -> (RealWorld, Char)

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

Но теперь мы пишем следующее:

тип IO = State RealWorld

getChar:: IO Char

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

Поэтому, когда программа Haskell хочет сменить лампочку, она захватывает лампу и применяет функцию "поворот" к значению RealWorld внутри IO.

Ответ 8

Для меня до сих пор объяснение, которое ближе всего связывает монады в теории категорий и монадах в Haskell, состоит в том, что монады - это monid, объекты которого имеют тип a- > m b. Я вижу, что эти объекты очень близки к endofunctor, и поэтому состав таких функций связан с императивной последовательностью программных операторов. Также функции, возвращающие функции ввода-вывода, действительны в чистом функциональном коде до тех пор, пока внутренняя функция не будет вызвана извне.

Этот id-элемент - это "a → m a", который очень хорошо вписывается, но элемент умножения представляет собой композицию функции, которая должна быть:

( >= > ):: Monad m = > (a → m b) → (b → m c) → (a → m c)

Это не совсем функциональный состав, но достаточно близко (я думаю, чтобы получить истинную композицию функции, нам нужна дополнительная функция, которая возвращает mb обратно в a, тогда мы получим композицию функции, если мы применим их попарно?), я не совсем уверен, как это получить от этого:

( → =):: Monad m = > m a → (a → m b) → m b

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

Другая вещь, которую я хотел бы сделать, - это связать все объяснения теории разных категорий: endofunctor + 2 естественных преобразования, категорию Клейсли, моноид, объекты которого являются моноидами и т.д. Для меня то, что, кажется, связывает все эти объяснения, состоит в том, что они два уровня. То есть, как правило, мы рассматриваем объекты категории как "черные ящики", где мы подразумеваем их свойства от их внешних взаимодействий, но здесь, похоже, нужно идти на один уровень внутри объектов, чтобы увидеть, что происходит? Мы можем объяснить монады без этого, но только если мы принимаем произвольные конструкции.

Martin

Ответ 9

Посмотрите на этот вопрос: - это цепочки операций, которые решает только класс монады?

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

С другой стороны, если заданный тип, который решает данную проблему, сталкивается с проблемой "цепочки операций с выбором", то он должен быть сделан экземпляром (наследованием) класса Monad.

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