Разные способы увидеть монаду

29

Во время изучения Haskell я столкнулся с множеством учебных пособий, в которых пытался объяснить, что такое монады и почему они важны в Haskell. Каждый из них использовал аналогии, чтобы было легче понять смысл. В конце концов, я получил 3 разных взгляда на то, что такое монада:

Вид 1: Монада как ярлык

Иногда мне кажется, что монада как ярлык для конкретного типа. Например, функция типа:

myfunction :: IO Int

myfunction - это функция, которая при каждом выполнении выдает значение Int. Тип результата - не Int, а IO Int. Итак, IO - это метка значения Int, предупреждающая пользователя о том, что значение Int является результатом процесса, в котором было выполнено действие IO.

Следовательно, это значение Int было помечено как значение, полученное из процесса с IO, поэтому это значение является «грязным». Ваш процесс больше не чист.

Вид 2: Монада как личное пространство, где могут происходить неприятные вещи.

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

Вид 3: Монада как в теории категорий

Это мнение, которое я не до конца понимаю. Монада - это просто функтор той же категории или подкатегории. Например, у вас есть значения Int и в качестве подкатегории IO Int, которые являются значениями Int, сгенерированными после процесса ввода-вывода.

Верны ли эти взгляды? Что является более точным?

Oni
источник
5
№ 2 не то, что монада вообще. Фактически, это в значительной степени ограничено IO, и не является полезным представлением (см., Что не является Монадой ). Кроме того, «строгий» обычно используется для обозначения свойства, которым Haskell не обладает (а именно, строгая оценка). Кстати, Монады это тоже не меняют (опять же, посмотрите, чем Монада не является).
3
Технически, только третий является правильным. Монада является эндофунктором, для которой определяются специальные операции - раскрутка и привязка. Монады многочисленны - список монада является идеальным примером, чтобы получить интуицию за монады. Удобства для чтения еще лучше. Удивительно, но монады можно использовать в качестве инструментов для неявной обработки потоков состояния на чистом функциональном языке. Это не определяющее свойство монад: это совпадение, что потоки состояний могут быть реализованы в их терминах. То же относится и к IO.
Permeakra
Common Lisp имеет свой собственный компилятор как часть языка. На Хаскеле есть монады.
Уилл Несс

Ответы:

33

Представления № 1 и № 2 в целом неверны.

  1. Любой тип данных * -> *может работать как метка, монады - гораздо больше.
  2. (За исключением IOмонады) вычисления внутри монады не являются нечистыми. Они просто представляют вычисления, которые мы воспринимаем как имеющие побочные эффекты, но они чисты.

Оба эти недоразумения происходят от сосредоточенности на IOмонаде, которая на самом деле немного особенная.

Я постараюсь немного подробнее остановиться на №3, не вдаваясь в теорию категорий, если это возможно.


Стандартные вычисления

Все вычисления в функциональном языке программирования можно рассматривать как функции с типом источника и целевого типа: f :: a -> b. Если функция имеет более одного аргумента, мы можем преобразовать ее в функцию с одним аргументом с помощью карри (см. Также вики Haskell ). И если у нас есть только значение x :: a(функция с 0 аргументов), мы можем превратить его в функцию , которая принимает аргумент типа блока : (\_ -> x) :: () -> a.

Мы можем создавать более сложные программы из более простых, составляя такие функции с помощью .оператора. Например, если у нас есть f :: a -> bи g :: b -> cмы получим g . f :: a -> c. Обратите внимание, что это работает и для наших преобразованных значений: если у нас есть x :: aи преобразовать его в наше представление, мы получаем f . ((\_ -> x) :: () -> a) :: () -> b.

Это представление имеет несколько очень важных свойств, а именно:

Монадические вычисления

Предположим, мы хотим выбрать и поработать с какой-то особой категорией вычислений, результат которой содержит нечто большее, чем просто возвращаемое значение. Мы не хотим уточнять, что означает «что-то большее», мы хотим сделать вещи как можно более общими. Самый общий способ представить «нечто большее» - это представить его как функцию типа - тип mтипа * -> *(то есть он преобразует один тип в другой). Поэтому для каждой категории вычислений, с которой мы хотим работать, у нас будет некоторая функция типа m :: * -> *. (В Haskell, mесть [], IO, Maybeи т.д.) И категория содержит все функции типов a -> m b.

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

  • Иметь оператор (назовем его <=<), который объединяет функции f :: a -> m bи g :: b -> m cпревращает их во что-то вроде g <=< f :: a -> m c. И это должно быть ассоциативно.
  • Чтобы иметь некоторую идентификационную функцию для каждого типа, давайте назовем ее return. Мы также хотим, чтобы f <=< returnэто было так же, как fи так же, как return <=< f.

Любой, m :: * -> *для которого у нас есть такие функции returnи <=<называется монадой . Это позволяет нам создавать сложные вычисления из более простых, как в базовом случае, но теперь типы возвращаемых значений преобразуются m.

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

Монады в Хаскеле

В Haskell (и других функциональных языках) мы в основном работаем со значениями, а не с функциями типов () -> a. Таким образом, вместо определения <=<для каждой монады, мы определяем функцию (>>=) :: m a -> (a -> m b) -> m b. Такое альтернативное определение эквивалентно, мы можем выразить, >>=используя <=<и наоборот (попробуйте в качестве упражнения, или посмотрите источники ). Принцип менее очевиден сейчас, но он остается тем же: наши результаты всегда имеют типы, m aи мы составляем функции типов a -> m b.

Для каждой монады, которую мы создаем, мы не должны забывать проверять это returnи <=<иметь требуемые нам свойства: ассоциативность и тождество слева / справа. Выражается с помощью returnи >>=они называются законами монады .

Пример - списки

Если мы решим mбыть [], мы получим категорию функций типов a -> [b]. Такие функции представляют недетерминированные вычисления, результатом которых может быть одно или несколько значений, но также нет значений. Это приводит к так называемой монаде списка . Состав f :: a -> [b]и g :: b -> [c]работает следующим образом: g <=< f :: a -> [c]означает вычислить все возможные результаты типа [b], применить gк каждому из них и собрать все результаты в один список. Выражается в Хаскеле

return :: a -> [a]
return x = [x]
(<=<) :: (b -> [c]) -> (a -> [b]) -> (a -> [c])
g (<=<) f  = concat . map g . f

или используя >>=

(>>=) :: [a] -> (a -> [b]) -> [b]
x >>= f  = concat (map f x)

Обратите внимание, что в этом примере возвращаемые типы были [a]настолько вероятными, что они не содержали никакого значения типа a. Действительно, для монады не существует такого требования, чтобы у возвращаемого типа были такие значения. У некоторых монад всегда есть (как IOили State), но у некоторых нет, как []или Maybe.

IO монада

Как я уже говорил, IOмонада - это нечто особенное. Значение типа IO aозначает значение типа, aсозданное путем взаимодействия с программной средой. Таким образом (в отличие от всех других монад), мы не можем описать значение типа, IO aиспользуя некоторую чистую конструкцию. Вот IOпросто тег или метка, которая отличает вычисления, которые взаимодействуют со средой. Это (единственный случай), когда представления № 1 и № 2 являются правильными.

Для IOмонады:

  • Состав f :: a -> IO bи g :: b -> IO cозначает: вычисление, fкоторое взаимодействует со средой, а затем вычисление, gкоторое использует значение и вычисляет результат, взаимодействующий со средой.
  • returnпросто добавляет IO«тег» к значению (мы просто «вычисляем» результат, сохраняя среду нетронутой).
  • Законы монады (ассоциативность, тождественность) гарантируются компилятором.

Некоторые заметки:

  1. Поскольку у монадических вычислений всегда есть тип результата m a, нет способа, как «убежать» от IOмонады. Смысл в следующем: как только вычисление взаимодействует со средой, вы не можете создать вычисление из него, которое этого не делает.
  2. Когда функциональный программист не знает , как сделать что - то в чистом виде, он (а) может (как последний курорт) программа задачи по некоторому состоянию вычислений внутри IOмонады. Именно поэтому IOего часто называют грехом программиста .
  3. Обратите внимание, что в нечистом мире (в смысле функционального программирования) чтение значения также может изменить среду (например, потреблять вводимые пользователем данные). Вот почему функции вроде getCharдолжны иметь тип результата IO something.
Петр Пудлак
источник
3
Отличный ответ. Я бы пояснил, что IOне имеет специальной семантики с точки зрения языка. Он не особенный, он ведет себя как любой другой код. Только реализация библиотеки времени выполнения является особенной. Также существует специальный способ escape ( unsafePerformIO). Я думаю, что это важно, потому что люди часто думают IOкак специальный элемент языка или декларативный тег. Нет.
USR
2
@usr Хорошо. Я бы добавил, что unsafePerformIO действительно небезопасен и должен использоваться только экспертами. Это позволяет вам ломать все, например, вы можете создать функцию, coerce :: a -> bкоторая преобразует любые два типа (и в большинстве случаев вылетает из программы). Посмотрите этот пример - вы можете преобразовать даже функцию в Intи т. Д.
Петр Пудлак
Другой монадой «особой магии» будет ST, которая позволяет вам объявлять ссылки на память, из которой вы можете читать и записывать, как вам удобно (хотя только в пределах монады), а затем вы можете извлечь результат, вызвавrunST :: (forall s. GHC.ST.ST s a) -> a
sara
5

Вид 1: Монада как ярлык

«Следовательно, это значение Int было помечено как значение, полученное из процесса с IO, поэтому это значение« грязное »».

«IO Int», как правило, не является значением Int (хотя в некоторых случаях это может быть, например, «return 3»). Это процедура, которая выводит некоторое значение Int. Разные исполнения этой «процедуры» могут давать разные значения Int.

Монада m является встроенным (обязательным) «языком программирования»: в этом языке можно определить некоторые «процедуры». Монадическое значение (типа ma) - это процедура на этом «языке программирования», которая выводит значение типа a.

Например:

foo :: IO Int

некоторая процедура, которая выводит значение типа Int.

Затем:

bar :: IO (Int, Int)
bar = do
  a <- foo
  b <- foo
  return (a,b)

это некоторая процедура, которая выводит два (возможно, разных) Ints.

Каждый такой «язык» поддерживает некоторые операции:

  • две процедуры (ma и mb) могут быть «сцеплены»: вы можете создать более крупную процедуру (ma >> mb), сделанную из первой, а не второй;

  • более того, выход (a) первого может повлиять на второй (ma >> = \ a -> ...);

  • процедура (возврат x) может дать некоторое постоянное значение (x).

Различные встроенные языки программирования различаются в зависимости от того, что они поддерживают:

  • получение случайных значений;
  • «разветвление» ([] монада);
  • исключения (бросить / поймать) (монада Either e);
  • явное продолжение / поддержка callcc;
  • отправка / получение сообщений другим «агентам»;
  • создавать, устанавливать и читать переменные (локальные для этого языка программирования) (монада ST).
ysdx
источник
1

Не путайте монадический тип с классом монад.

Монадический тип (т. Е. Тип, являющийся экземпляром класса монад) решит конкретную проблему (в принципе, каждый монадический тип решает свою задачу): State, Random, Maybe, IO. Все они являются типами с контекстом (то, что вы называете «меткой», но это не то, что делает их монадой).

Для всех из них существует необходимость в «операциях с выбором цепочки» (одна операция зависит от результата предыдущей). Здесь вступает в игру класс монада: пусть ваш тип (решение данной проблемы) будет экземпляром класса монады, и проблема цепочки решена.

Посмотрите, что решает класс монада?

cibercitizen1
источник