Монада (функциональное программирование)

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Май 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

• Один для обертывания значений любого базового типа внутри монады (с получением монадического значения );
• Другой - для составления функций , выводящих монадические значения (называемые монадическими функциями ). ^[1]

Это позволяет монадам упростить широкий круг проблем, таких как обработка потенциальных неопределенных значений (с помощью Maybeмонады) или сохранение значений в гибком, правильно сформированном списке (с использованием Listмонады). С помощью монады программист может превратить сложную последовательность функций в лаконичный конвейер, который абстрагирует управление вспомогательными данными, поток управления или побочные эффекты . ^{[1] [2]}

И концепция монады, и термин первоначально пришли из теории категорий , где монада определяется как функтор с дополнительной структурой. ^[a] Исследования, начатые в конце 1980-х - начале 1990-х годов, установили, что монады могут решать, казалось бы, разрозненные проблемы информатики в рамках единой функциональной модели. Теория категорий также предоставляет несколько формальных требований, известных как законы монад , которым должна удовлетворять любая монада и которые могут использоваться для проверки монадического кода. ^{[3] [4]}

Поскольку монады делают семантику явной для своего рода вычислений, их также можно использовать для реализации удобных языковых функций. Некоторые языки, такие как Haskell , даже предлагают предварительно созданные определения в своих основных библиотеках для общей структуры монад и общих экземпляров. ^{[1] [5]}

Обзор [ править ]

«Для монады mзначение типа m aпредставляет доступ к значению типа aв контексте монады». —Ка Макканн ^[6]

Монада может быть создана путем определения конструктора типа M и двух операций: return(часто также называемых единицей ), которая получает значение типа aи превращает их в монадическое значение типа m aс помощью конструктора типа; и bind(обычно представлен как >>=), который получает функцию fпо типу aи может преобразовывать монадические значения, m aприменяемые fк развернутому значению a. (Альтернативную, но эквивалентную конструкцию с использованием join функции вместо bindоператора можно найти в более позднем разделе « Получение из функторов ».)

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

Между каждой парой составных вызовов функций оператор связывания >>=может ввести в монадическое значение m aнекоторую дополнительную информацию, которая недоступна внутри функции f, и передать ее по конвейеру. Он также может более точно контролировать поток выполнения, например, вызывая функцию только при определенных условиях или выполняя вызовы функции в определенном порядке.

Пример: Может быть [ править ]

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

Первым шагом к этой цели может быть создание типа опции, который будет отмечать значение как несущее значение некоторого типа T( Tможет быть любого типа) или не имеющее значения. Будет вызван новый тип, Maybe Tи значения этого типа могут либо содержать значение типа T, либо быть пустым значением Nothing. Значение Xтипа , Tкоторый определен , но используется в контексте Maybeбудет называться Just X. Это сделано, чтобы избежать путаницы, путем различения случаев, когда переменная несет определенное значение, и тех, где это не так.

данные  Может быть  T  =  Просто  T  или  ничего

Maybe Tможет пониматься как «оборачивающий» тип, оборачивающий тип Tв новый тип со встроенной обработкой исключений, но не содержащий информации о причине исключения.

В следующем коде переменные с префиксом mимеют тип Maybe Tдля определенного типа T. Например, если переменная mxсодержит значение, то именно там Just x, где переменная xимеет тип T. λx → ...является анонимной функцией с параметром x, тип которого определяется , и ∘является оператором композиции функции .

Еще одно улучшение было бы, если бы функция могла управлять простыми проверенными исключениями с Maybeтипом, закорачивая и возвращая Nothingпри сбое шага, но возвращая правильное значение без комментариев, если вычисление завершается успешно.

Функция сложения add, которая делает именно это при добавлении двух Maybeзначений mxи my, может быть определена следующим образом:

 add  :  ( Может быть,  Число ,  Может быть,  Число )  →  Может быть  Число  add ( mx , my )  =  ...  если  mx  равно  Ничего,  тогда  ...  Ничего  другого,  если  my  равно  Ничего,  тогда  ...  Ничего  другого  ...  Просто  ( x  +  y )  конец,  если

Однако написание функций, обрабатывающих Maybeзначения от случая к случаю, может быть утомительным и станет еще более трудоемким по мере определения большего количества функций. Операция по объединению шагов в цепочку - один из способов облегчить это, и с помощью инфиксного оператора, такого как x >>= y, он может даже интуитивно представить передачу (возможно, неопределенного) результата каждого шага в следующий. Однако, поскольку каждый результат технически вставлен в другую функцию , оператор примет функцию в качестве параметра. Поскольку addуже указан тип его выходного значения, не должно мешать сохранить гибкость оператора и принимать функции, которые выводят разные типы из своего ввода:

 >> =  :  ( Возможно  T ,  T  →  Может быть  U )  →  Может быть  U  ( mx  >> =  f )  =  ...  если  mx  равно  ( Just  x ),  то  ...  f ( x )  - f возвращает определенное значение type Maybe U  else  ...  Nothing  - f не возвращает значение  end  if

С >>=доступны, addтеперь могут быть переопределены как нечто гораздо более компактен:

 добавить ( mx , my )  =  mx  >> =  λx  ->  ( my  >> =  λy  ->  Just  ( x  +  y ))

Это более кратко, но небольшой дополнительный анализ открывает нечто еще более мощное. Во-первых, единственная роль, которая Justиграет здесь, add- это пометить базовое значение как Maybeзначение. Чтобы подчеркнуть, как Just действует на базовое значение, заключая его в оболочку, его также можно переопределить как функцию, вызываемую etaсейчас:

 eta  :  T  →  Может быть,  T  eta ( x )  =  Just  x

Большая картина такова , что эти две функции >>=и etaбыли разработаны , чтобы упростить add, но они явно не зависят от специфики addв любом пути, просто Maybeтипа. Фактически, эти функции могут применяться к любым значениям и функциям данного Maybeтипа, независимо от типов базовых значений. Например, вот краткий оператор НЕ из троичной логики (Клини), который использует те же функции для автоматизации неопределенных значений:

trinot  :  Может быть,  логическое  →  Может быть,  логическое trinot ( mp )  =  mp  >> =  λp  ->  ( eta  ∘  not )  p

Оказывается, Maybeтип вместе с >>=и etaобразует монаду. В то время как другие монады будут воплощать разные логические процессы, а некоторые могут иметь дополнительные свойства, все они будут иметь три одинаковых компонента (прямо или косвенно), которые следуют основной схеме этого примера. ^{[1] [7]}

Определение [ править ]

Более общее определение монады в функциональном программировании, используемое в приведенном выше примере, фактически основано на тройке Клейсли, а не на стандартном определении теории категорий. Однако две конструкции оказываются математически эквивалентными, поэтому любое определение даст действительную монаду. Для любых четко определенных базовых типов T , U монада состоит из трех частей:

• Конструктор типа М , который строит монадические типа MT ^[B]
• Преобразователь типа , часто называемый блок или возврата , который встраивает объект х в монаде:
  unit(x) : T → M T^[c]
• Комбинатор , как правило , называют связыванием (как в связывании переменного ) и представлен с оператором инфиксным >>= , что разворачивает монадическую переменный, а затем вставляет его в монадическую функции / выражение, в результате чего в новом монадического значения:
  (mx >>= f) : (M T, T → M U) → M U^[d]

Однако, чтобы полностью квалифицироваться как монада, эти три части должны также соответствовать нескольким законам:

• unit - это левая идентичность для связывания :
  unit(a) >>= λx → f(x) ↔ f(a)
• unit также является идентификатором для привязки :
  ma >>= λx → unit(x) ↔ ma
• bind по существу ассоциативен : ^[e]
  ma >>= λx → (f(x) >>= λy → g(y)) ↔ (ma >>= λx → f(x)) >>= λy → g(y)^[1]

Алгебраически, это означает любой монады и приводит к категории (называемой категории Клейсли ) и в моноид в категории функторов (от значений до вычислений), с монадической композиции в виде двоичного оператора и единицы в качестве идентичности. ^{[ необходима цитата ]}

Использование [ править ]

Значение шаблона монады выходит за рамки простого уплотнения кода и предоставления ссылки на математические рассуждения. Какой бы язык или парадигма программирования по умолчанию не использовала разработчик, следование шаблону монады дает многие преимущества чисто функционального программирования . По материализации конкретного вида вычислений, монады не только инкапсулируют утомительные детали этой вычислительной модели, но делает это в декларативном образом, улучшая четкость в коде. Поскольку монадические значения явно представляют не только вычисленные значения, но и вычисленные эффекты , монадическое выражение может быть заменено своим значением в ссылочно прозрачных позициях., очень похоже на чистые выражения, допускающие множество методов и оптимизаций, основанных на переписывании . ^[4]

Обычно программисты используют связывание для объединения монадических функций в последовательность, что привело к тому, что некоторые из них описали монады как «программируемые точки с запятой», указание на то, сколько императивных языков используют точки с запятой для разделения операторов . ^{[1] [5]} Однако следует подчеркнуть, что монады на самом деле не упорядочивают вычисления; даже в языках, которые используют их как центральные функции, более простая композиция функций может упорядочивать шаги в программе. Общая полезность монады заключается, скорее, в упрощении структуры программы и улучшении разделения задач посредством абстракции. ^{[4] [9]}

Структуру монады также можно рассматривать как уникальную математическую вариацию и вариацию времени компиляции в шаблоне декоратора . Некоторые монады могут передавать дополнительные данные, которые недоступны функциям, а некоторые даже обеспечивают более тонкий контроль над выполнением, например, вызывая функцию только при определенных условиях. Поскольку они позволяют прикладным программистам реализовывать логику предметной области, одновременно выгружая шаблонный код на предварительно разработанные модули, монады можно даже рассматривать как инструмент для аспектно-ориентированного программирования . ^[10]

Еще одно заслуживающее внимания использование монад - это изоляция побочных эффектов, таких как ввод / вывод или изменяемое состояние , в чисто функциональном коде. Даже чисто функциональные языки могут по- прежнему реализовывать эти «нечистые» вычисления без монад, в частности, посредством сложного сочетания композиции функций и стиля передачи продолжения (CPS). ^{[2] Однако с} помощью монад большую часть этого каркаса можно абстрагировать, по существу, беря каждый повторяющийся шаблон в коде CPS и объединяя его в отдельную монаду. ^[4]

Если язык не поддерживает монады по умолчанию, все еще можно реализовать шаблон, часто без особых трудностей. При переводе из теории категорий в термины программирования структура монады является общим понятием и может быть определена непосредственно на любом языке, который поддерживает эквивалентную функцию для ограниченного полиморфизма . Способность концепта оставаться агностическим в отношении рабочих деталей при работе с базовыми типами - это мощно, но уникальные особенности и строгое поведение монад отличают их от других концепций. ^[11]

Приложения [ править ]

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

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

• Библиотека парсера Parsec использует монады для комбинирования более простых правил синтаксического анализа с более сложными и особенно полезна для небольших предметно-ориентированных языков . ^[12]
• xmonad - это тайловый оконный менеджер, основанный на структуре данных застежки-молнии , которая сама по себе может рассматриваться монадически как частный случай продолжений с разделителями . ^[13]
• LINQ от Microsoft предоставляет язык запросов для .NET Framework, на который сильно влияют концепции функционального программирования, включая основные операторы для монадического составления запросов. ^[14]
• ZipperFS - это простая экспериментальная файловая система, которая также использует структуру застежки-молнии в первую очередь для реализации своих функций. ^[15]
• Реактивные расширения рамка по существу представляет собой (со) монадическим интерфейс для потоков данных , реализующего шаблон наблюдателя . ^[16]

История [ править ]

Термин «монада» в программировании фактически восходит к языкам программирования APL и J , которые имеют тенденцию быть чисто функциональными. Однако в этих языках «монада» - это только сокращение для функции, принимающей один параметр (функция с двумя параметрами, являющаяся «диадой», и т. Д.). ^[17]

Математик Роджер Годеман был первым, кто сформулировал концепцию монады (назвав ее «стандартной конструкцией») в конце 1950-х годов, хотя термин «монада», который стал доминирующим, был популяризирован теоретиком категорий Сондерсом Мак Лейном . ^{[ необходима цитата ]} Форма, определенная выше с использованием связывания , однако, была первоначально описана в 1965 году математиком Генрихом Клейсли , чтобы доказать, что любую монаду можно охарактеризовать как присоединение между двумя (ковариантными) функторами. ^[18]

Начиная с 1980-х, в компьютерном сообществе начало появляться расплывчатое представление о шаблоне монад. По словам исследователя языков программирования Филипа Уодлера , компьютерный ученый Джон Рейнольдс предвидел несколько аспектов этого в 1970-х и начале 1980-х, когда он обсуждал ценность стиля передачи продолжения , теорию категорий как богатый источник формальной семантики и тип различие между ценностями и вычислениями. ^[4] Исследовательский язык Opal , который активно разрабатывался до 1990 г., также эффективно основывал ввод-вывод на монадическом типе, но в то время связь не была реализована. ^[19]

Ученый-компьютерщик Эудженио Моджи был первым, кто явно связал монаду теории категорий с функциональным программированием в докладе на конференции в 1989 г. ^[20], за которым последовало более изысканное представление в журнале в 1991 г. В более ранней работе несколько ученых-информатиков продвинулись в использовании теория категорий для обеспечения семантики лямбда-исчисления . Ключевой вывод Моджи заключался в том, что реальная программа - это не просто функция от значений к другим значениям, а скорее преобразование, которое формирует вычисления для этих значений. При формализации в терминах теории категорий это приводит к выводу, что монады являются структурой для представления этих вычислений. ^[3]

Несколько других популяризировали и построили эту идею, в том числе Филип Уодлер и Саймон Пейтон Джонс , оба из которых принимали участие в спецификации Haskell. В частности, Haskell использовал проблемную модель «ленивого потока» вплоть до версии 1.2 для согласования ввода-вывода с отложенным вычислением , пока не переключился на более гибкий монадический интерфейс. ^[21] Сообщество Haskell продолжит применять монады для решения многих задач функционального программирования, и в 2010-х годах исследователи, работающие с Haskell, в конце концов осознали, как монады связаны с другими структурами, такими как аппликативные функторы и стрелки . ^{[ необходима цитата ]}

Сначала программирование с помощью монад в основном ограничивалось Haskell и его производными, но поскольку функциональное программирование повлияло на другие парадигмы, многие языки включили шаблон монады (по духу, если не по названию). Формулировки теперь существуют в Scheme , Perl , Python , Racket , Clojure , Scala , F # , а также были рассмотрены для нового стандарта машинного обучения. ^{[ необходима цитата ]}

Анализ [ править ]

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

Проверка законов монад [ править ]

Возвращаясь к Maybeпримеру, было объявлено, что его компоненты составляют монаду, но не было дано никаких доказательств того, что она удовлетворяет законам монад.

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

Закон 1: eta (a) >> = f (x) ⇔ (Just a) >> = f (x) ⇔ f (a)

Закон 2: ma >> = eta (x) ⇔ ma если ма является (Просто) , то eta (a) ⇔ Просто иначе  или Ничего ⇔ Ничего конец, если

Закон 3:  ( ma >> = f (x) ) >> = g (y) ⇔ ma >> = ( f (x) >> = g (y) ) если (ma >> = f (x)) равно (Just b), то  если ma равно (Just a), то g (ma >> = f (x)) (f (x) >> = g (y)) а еще  другое Ничего ничего конец, если  конец, если ⇔ если ma равно (Just a) и f (a) is (Just b), то  (g ∘ f) а иначе, если ma равно (Just a) и f (a) равно Nothing, то Ничего еще Ничего конец, если

Вывод из функторов [ редактировать ]

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

Однако это не всегда является серьезной проблемой, особенно когда монада является производной от уже существующего функтора, после чего монада автоматически наследует map . (По историческим причинам это mapвместо этого называется fmapв Haskell.)

Первое преобразование монады на самом деле является той же единицей из тройки Клейсли, но, внимательно следуя иерархии структур, оказывается, что единица характеризует аппликативный функтор , промежуточную структуру между монадой и базовым функтором. В прикладном контексте unit иногда называют чистым, но это все равно та же функция. Что действительно отличается в этой конструкции, так это то, что единица закона должна удовлетворять; поскольку привязка не определена, ограничение задается в терминах карты :

Последний скачок от аппликативного функтора к монаде происходит со вторым преобразованием, функцией соединения (в теории категорий это естественное преобразование, обычно называемое μ ), которое «выравнивает» вложенные приложения монады:

В качестве характеристической функции, присоединиться также должно удовлетворять три вариации законов монад: ^{[ править ]}

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

Другой пример: Список [ редактировать ]

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

Встраивание простого значения в список также тривиально для большинства языков:

unit (x) = [x]

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

Однако процедура применения любой простой функции ко всему списку, другими словами map , проста:

(отображение φ) xlist = [φ (x1), φ (x2), ..., φ (xn)]

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

join (xlistlist) = join ([xlist1, xlist2, ..., xlistn]) = xlist1 ++ xlist2 ++ ... ++ xlistn

Результирующая монада представляет собой не только список, но и тот, который автоматически изменяет размер и уплотняет себя по мере применения функций.bind теперь также можно получить с помощью формулы, а затем использовать для Listпередачи значений через конвейер монадических функций:

(xlist >> = f) = присоединиться ∘ (map f) xlist

Одно приложение для этого монадического списка представляет недетерминированные вычисления .Listможет хранить результаты для всех путей выполнения в алгоритме, а затем уплотнять себя на каждом шаге, чтобы «забыть», какие пути привели к каким результатам (иногда важное отличие от детерминированных исчерпывающих алгоритмов). ^{[ необходима цитата ]} Еще одно преимущество - то, что проверки могут быть встроены в монаду; определенные пути могут быть прозрачно сокращены в их первой точке отказа, без необходимости переписывать функции в конвейере. ^[23]

Вторая ситуация, когда Listлучше всего подходит, - это составление многозначных функций . Например, комплексный корень n- го числа из числа должен давать n различных комплексных чисел, но если затем взять другой корень m- й степени из этих результатов, окончательные значения m • n должны быть идентичны выходным данным корня m • n- й степени. . полностью автоматизирует эту проблему, объединяя результаты каждого шага в плоский, математически правильный список. ^[24]List

Методы [ править ]

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

Синтаксическая нотация сахара [ править ]

Хотя использование привязки открыто часто имеет смысл, многие программисты предпочитают синтаксис , который имитирует императивные высказывания ( так называемых делать-обозначение в Haskell, выполнять нотации в OCaml , вычисление выражение в F # , ^[25] и для понимания в Scala ). Это всего лишь синтаксический сахар, который маскирует монадический конвейер под кодовый блок ; затем компилятор незаметно переведет эти выражения в базовый функциональный код.

Перевод addфункции из языка MaybeHaskell может показать эту возможность в действии. Немонадическая версия addв Haskell выглядит так:

add  mx  my  =  case  mx  of  Nothing  ->  Nothing  Just  x  ->  case  my  of  Nothing  ->  Nothing  Just  y  ->  Just  ( x  +  y )

В монадическом Haskell returnэто стандартное имя для единицы , плюс лямбда-выражения должны обрабатываться явно, но даже с этими техническими особенностями Maybeмонада делает более четкое определение:

добавить  mx  my  =  mx  >> =  ( \ x  ->  my  >> =  ( \ y  ->  return  ( x  +  y )))

Тем не менее, с помощью do-notation это может быть переработано еще дальше в очень интуитивно понятную последовательность:

add  mx  my  =  do  x  <-  mx  y  <-  my  return  ( x  +  y )

Второй пример показывает, как Maybeможно использовать совершенно другой язык: F #. С помощью вычислительных выражений функция «безопасного деления», возвращающая Noneнеопределенный операнд или деление на ноль, может быть записана как:

let  readNum  ()  =  let  s  =  Console . ReadLine ()  пусть  succ , v  =  Int32 . TryParse ( s )  if  ( succ )  then  Some ( v )  else  Nonelet  secure_div  =  возможно  {  let !  x  =  readNum ()  пусть !  y  =  readNum ()  if  ( y  =  0 )  then  None  else  return  ( x  /  y )  }

Во время сборки компилятор внутренне «обезвожит» эту функцию, превратив ее в более плотную цепочку вызовов связывания :

может быть . Задержка ( весело  ()  ->  возможно . Bind ( readNum () ,  весело  х  ->  возможно . Bind ( readNum () ,  весело  у  ->  если  ( у = 0 ) ,  то  None  еще  возможно . Возврат ( х  /  у ))) )

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

do  {  x  <-  вернуть  v ;  f  x  }  ==  делать  {  f  v  } делать  {  x  <-  m ;  return  x  }  ==  do  {  m  } do  {  y  <-  do  {  x  <-  m ;  f  x  };  г  у  }  ==  делать  {  х  <-  м ;  y  <-  f  x ;  грамм y  }

Хотя это и удобно, разработчик всегда должен помнить, что этот стиль блока является чисто синтаксическим и может быть заменен внешне монадическими (или даже немонадическими) выражениями. Использование bind для выражения монадического конвейера во многих случаях все еще может быть более ясным, и некоторые сторонники функционального программирования даже утверждают, что, поскольку блочный стиль позволяет новичкам переносить привычки из императивного программирования, его следует избегать по умолчанию и использовать только тогда, когда он явно превосходит. ^{[26] [1]}

Общий интерфейс [ править ]

Каждая монада нуждается в особой реализации, которая соответствует законам монад, но другие аспекты, такие как отношение к другим структурам или стандартные идиомы в пределах языка, являются общими для всех монад. В результате язык или библиотека могут предоставлять общий Monadинтерфейс с прототипами функций , отношениями подтипов и другими общими фактами. Помимо обеспечения старта для разработки и гарантии того, что новая монада наследует свойства супертипа (например, функторы), проверка дизайна монады по интерфейсу добавляет еще один уровень контроля качества. ^{[ необходима цитата ]}

Операторы [ редактировать ]

Монадический код часто можно еще больше упростить за счет разумного использования операторов. Функционал карты может быть особенно полезен, поскольку он работает не только с одноранговыми монадическими функциями; до тех пор, пока монадическая функция должна работать аналогично предопределенному оператору, можно использовать map , чтобы мгновенно « поднять » более простой оператор в монадический. ^[f] С помощью этого метода определение addиз Maybeпримера можно разделить на:

добавить (mx, my) = карта (+)

Процесс можно продвинуть еще на один шаг, определив addне только для Maybe, но и для всего Monadинтерфейса. Таким образом, любая новая монада, которая соответствует интерфейсу структуры и реализует свою собственную карту , немедленно унаследует также повышенную версию add. Единственное необходимое изменение функции - это обобщение сигнатуры типа:

добавить: (Число монады, Число монады) → Число монады [27]

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

(f> => g) x = (f (x) → mb) >> = g (y = b)

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

(единица измерения> => г) ↔ г(f> => единица) ↔ f(f> => g)> => h ↔ f> => (g> => h) [1]

Варианты [ править ]

На математическом уровне некоторые монады обладают особенно хорошими свойствами и однозначно подходят для решения определенных задач.

Аддитивные монады [ редактировать ]

Добавка монада является монадой наделен дополнительным замкнутым, ассоциативным, бинарным оператора Mplus и единичного элементом под Mplus , называемая mzero . MaybeМонаду можно считать добавку, с , Nothingкак mzero и вариация на OR оператор , как Mplus . Listтакже является аддитивной монадой, где пустой список []действует как mzero, а оператор конкатенации - ++как mplus .

Интуитивно mzero представляет собой монадическую оболочку без значения из базового типа, но также считается «нулем» (а не « единицей »), поскольку он действует как поглотитель для связывания , возвращая mzero всякий раз, когда он привязан к монадической функции. Это свойство двустороннее, и bind также вернет mzero, когда какое-либо значение привязано к монадической нулевой функции .

В терминах теории категорий аддитивная монада квалифицируется как моноид над монадическими функциями с bind (как и все монады), а затем над монадическими значениями через mplus . ^{[28] [г]}

Бесплатные монады [ редактировать ]

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

Например, работая полностью через Justи Nothingмаркер, то Maybeмонада фактически свободная монада. С Listдругой стороны, монада не является свободной монадой, поскольку она вносит в свое определение дополнительные, конкретные факты о списках (например, добавление ). Последний пример - это абстрактная свободная монада, использующая маркеры типа для единицы и привязки, а также рекурсивный конструктор линейного типа:

newtype Free F (T) = Unit T или Bind (F, Free F (T))unit (x) = Unit xmx >> = f = ... если mx - единица x, то ... f (x) еще ... Привязать (f, mx) конец, если

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

Намеренное использование свободных монад поначалу может показаться непрактичным, но их формальный характер особенно хорошо подходит для синтаксических задач. Свободную монаду можно использовать для отслеживания синтаксиса и типа, оставляя семантику на потом, и в результате она нашла применение в синтаксических анализаторах и интерпретаторах . ^[29] Другие применяли их и к более динамичным, оперативным задачам, таким как предоставление итераций в пределах языка. ^[30]

Комонады [ редактировать ]

Помимо создания монад с дополнительными свойствами, для любой данной монады также можно определить комонаду . Концептуально, если монады представляют вычисления, основанные на базовых значениях, тогда комонады можно рассматривать как редукции обратно к значениям. Монадический код, в некотором смысле, не может быть полностью «распакован»; как только значение помещается в монаду, оно остается там на карантине вместе с любыми побочными эффектами (что хорошо в чисто функциональном программировании). Однако иногда проблема больше связана с потреблением контекстных данных, которые комонады могут моделировать явным образом.

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

• Конструктор типа W, который отмечает тип WT более высокого порядка.
• Сопряженное блок , называемый коединица здесь, извлекает лежащее в основе значения из комонады:

count (wa): WT → T

• Обращение связывания (также представленное с помощью =>>), которое расширяет цепочку сокращающих функций:

(wa = >> f): (WU, WU → T) → WT [h]

Расширение и счет также должны удовлетворять двойственным законам монад:

счет ∘ ( (wa = >> f) → wb ) ↔ f (wa) → bва = >> счет ↔ ваwa ( (= >> f (wx = wa)) → wb (= >> g (wy = wb)) → wc ) ↔ ( wa (= >> f (wx = wa)) → wb ) (= >> g (wy = wb)) → wc

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

• duplicate принимает уже комонадическое значение и обертывает его другим слоем комонадической структуры:

дубликат (wa): WT → W (WT)

В то время как такие операции , как продлить перепутаны, однако, комонада делает не обратные функции он действует на, и , следовательно, comonads еще функторы с картой , а не кофункторами . Альтернативное определение с duplicate , counit и map также должно соответствовать собственным законам комонад:

((дубликат карты) ∘ дубликат) wa ↔ (дубликат ∘ дубликат) ва ↔ wwwa((счетчик карты) ∘ дубликат) ва ↔ (счетчик ∘ дубликат) ва ↔ ва((карта карты φ) ∘ дублировать) wa ↔ (дублировать ∘ (карта φ)) wa ↔ wwb

Как и в случае с монадами, две формы могут быть преобразованы автоматически:

(отображение φ) wa ↔ wa = >> (φ ∘ counit) wxдубликат wa ↔ wa = >> wx

wa = >> f (wx) ↔ ((карта f) ∘ дублировать) wa

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

Менее тривиальным примером является комонада Stream , которую можно использовать для представления потоков данных и присоединения фильтров к входящим сигналам с расширением . Фактически, хотя комонады не так популярны, как монады, исследователи обнаружили, что комонады особенно полезны для потоковой обработки и моделирования программирования потоков данных . ^{[31] [32]}

Однако из-за их строгих определений нельзя просто перемещать объекты между монадами и комонадами. Как еще более высокая абстракция, стрелки могут включать в себя обе структуры, но поиск более детальных способов комбинирования монадического и комонадического кода является активной областью исследований. ^{[33] [34]}

Больше примеров [ править ]

Монада идентичности [ править ]

Простейшая монада - это монада Identity , которая просто аннотирует простые значения и функции, чтобы удовлетворить законам монад:

идентификатор нового типа T = Tunit (x) = x(х >> = е) = е (х)

Identityдействительно имеет допустимое применение, например, в качестве базового случая для рекурсивных преобразователей монад . Его также можно использовать для выполнения основного назначения переменных в блоке императивного стиля. ^{[i] [ необходима ссылка ]}

Коллекции [ править ]

Любая коллекция с правильным добавлением уже является свободным моноидом, но оказывается, что Listэто не единственная коллекция, которая также имеет четко определенное соединение и квалифицируется как монада. Можно даже Listпреобразовать в эти другие монадические коллекции, просто наложив специальные свойства на append : ^{[j] [ необходима ссылка ]}

Монада ввода-вывода (Haskell) [ редактировать ]

Как уже упоминалось, чистый код не должен иметь неуправляемых побочных эффектов, но это не мешает программе явно описывать и управлять эффектами. Эта идея является центральной для монады ввода-вывода Haskell , где объект типа IO aможет рассматриваться как содержащий текущее состояние мира вне программы и вычисляющий значение типа a. Вычисление, которое не вычисляет никакого значения, то есть процедура, имеет тип IO (), « вычисляющий » фиктивное значение (). Когда программист связывает IOзначение с функцией, функция принимает решения на основе этого представления о мире (ввод от пользователей, файлов и т. Д.), А затем выдает монадическое значение, отражающее новое состояние мира (вывод программы). ^[21]

Например, в Haskell есть несколько функций для работы с более широкой файловой системой , в том числе одна, которая проверяет, существует ли файл, а другая - удаляет файл. Их сигнатуры двух типов:

doesFileExist  ::  FilePath  ->  IO  Bool removeFile  ::  FilePath  ->  IO  ()

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

IOоднако не ограничивается только файловым вводом-выводом; он даже позволяет пользователю ввод-вывод и, наряду с императивным синтаксическим сахаром, может имитировать типичное «Hello, World!». программа :

main  ::  IO  () main  =  do  putStrLn  "Привет, мир!"  putStrLn  "Как вас зовут, пользователь?"  name  <-  getLine  putStrLn  ( "Приятно познакомиться,"  ++  name  ++  "!" )

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

main  ::  IO  () main  =  putStrLn  "Привет, мир!"  >>  putStrLn  "Как тебя зовут, пользователь?"  >>  getLine  >> =  ( \ name  ->  putStrLn  ( "Приятно познакомиться,"  ++  name  ++  "!" ))

Монада писателя (JavaScript) [ редактировать ]

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

Чтобы показать, как шаблон монада не ограничивается преимущественно функциональными языками, в этом примере Writerмонада реализуется в JavaScript . Во-первых, массив (с вложенными хвостами) позволяет построить Writerтип как связанный список . Базовое выходное значение будет находиться в позиции 0 массива, а позиция 1 неявно будет содержать цепочку вспомогательных заметок:

констант  писатель  =  [ значение ,  []];

Определить единицу также очень просто:

const  unit  =  значение  =>  [ значение ,  []];

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

const в  квадрате  =  x  =>  [ x  *  x ,  [ ` $ { x } возведен в квадрат.` ]]; const  уменьшено вдвое  =  x  =>  [ x  /  2 ,  [ ` $ { x } было уменьшено вдвое.` ]];

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

const  bind  =  ( писатель ,  преобразование )  =>  {  const  [ значение ,  журнал ]  =  писатель ;  const  [ результат ,  обновления ]  =  преобразование ( значение );  return  [ результат ,  журнал . concat ( обновления )]; };

Примеры функций теперь можно объединить в цепочку с помощью связывания , но определение версии монадической композиции (называемой pipelogздесь) позволяет применять эти функции еще более кратко:

const  pipelog  =  ( писатель ,  ... преобразовывает )  =>  преобразовывает . уменьшить ( привязать ,  писатель );

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

трубовщик ( агрегат ( 4 ),  квадрат ,  разрезанный пополам ); // Полученный объект записи = [8, ['4 возведено в квадрат.', '16 было уменьшено вдвое.']]

Монада среды [ править ]

Среда монада (также называемая читатель монадой и функция монадой ) позволяет вычисление зависит от значения от общей окружающей среды. Конструктор типа монады отображает тип T на функции типа E → T , где E - тип разделяемой среды. Функции монады:

${\displaystyle {\begin{array}{ll}{\text{return}}\colon &T\rightarrow E\rightarrow T=t\mapsto e\mapsto t\\{\text{bind}}\colon &(E\rightarrow T)\rightarrow (T\rightarrow E\rightarrow T')\rightarrow E\rightarrow T'=r\mapsto f\mapsto e\mapsto f\,(r\,e)\,e\end{array}}}$

Полезны следующие монадические операции:

${\displaystyle {\begin{array}{ll}{\text{ask}}\colon &E\rightarrow E={\text{id}}_{E}\\{\text{local}}\colon &(E\rightarrow E)\rightarrow (E\rightarrow T)\rightarrow E\rightarrow T=f\mapsto c\mapsto e\mapsto c\,(f\,e)\end{array}}}$

Операция ask используется для получения текущего контекста, в то время как local выполняет вычисление в измененном подконтексте. Как и в монаде состояний, вычисления в монаде среды могут быть вызваны простым предоставлением значения среды и применением его к экземпляру монады.

Формально значение в монаде среды эквивалентно функции с дополнительным анонимным аргументом; return и bind эквивалентны комбинаторам K и S соответственно в исчислении комбинатора SKI .

Монады состояний [ править ]

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

Тип  Состояние  s  t  =  s  ->  ( t ,  s )

Обратите внимание, что эта монада принимает параметр типа, тип информации о состоянии. Операции с монадой определяются следующим образом:

- «return» производит заданное значение без изменения состояния. return  x  =  \ s  ->  ( x ,  s ) - "bind" изменяет m так, что он применяет f к своему результату. m  >> =  f  =  \ r  ->  пусть  ( x ,  s )  =  m  r  in  ( f  x )  s

К полезным операциям с состоянием относятся:

get  =  \ s  ->  ( s ,  s )  - Изучить состояние в этой точке вычислений. положить  s  =  \ _  ->  ( () ,  s )  - Заменить состояние. изменить  f  =  \ s  ->  ( () ,  f  s )  - Обновить состояние

Другая операция применяет монаду состояния к данному начальному состоянию:

runState  ::  State  s  a  ->  s  ->  ( a ,  s ) runState  t  s  =  t  s

do-блоки в монаде состояний - это последовательности операций, которые могут проверять и обновлять данные состояния.

Неформально монада состояния типа состояния S отображает тип возвращаемых значений T в функции типа , где S - это базовое состояние. Функции возврата и привязки :${\displaystyle S\rightarrow T\times S}$

${\displaystyle {\begin{array}{ll}{\text{return}}\colon &T\rightarrow S\rightarrow T\times S=t\mapsto s\mapsto (t,s)\\{\text{bind}}\colon &(S\rightarrow T\times S)\rightarrow (T\rightarrow S\rightarrow T'\times S)\rightarrow S\rightarrow T'\times S\ =m\mapsto k\mapsto s\mapsto (k\ t\ s')\quad {\text{where}}\;(t,s')=m\,s\end{array}}}$.

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

Монада продолжения [ править ]

Продолжение монада с обратным типом R отображает тип T в функцию типа . Он используется для моделирования стиля передачи продолжения . Функции возврата и связывания следующие:${\displaystyle \left(T\rightarrow R\right)\rightarrow R}$

${\displaystyle {\begin{array}{ll}{\text{return}}\colon &T\rightarrow \left(T\rightarrow R\right)\rightarrow R=t\mapsto f\mapsto f\,t\\{\text{bind}}\colon &\left(\left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T'\rightarrow R\right)\rightarrow R=c\mapsto f\mapsto k\mapsto c\,\left(t\mapsto f\,t\,k\right)\end{array}}}$

Функция call-with-current-continue определяется следующим образом:

${\displaystyle {\text{call/cc}}\colon \ \left(\left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R=f\mapsto k\mapsto \left(f\left(t\mapsto x\mapsto k\,t\right)\,k\right)}$

Журнал программы [ править ]

Следующий код - псевдокод. Предположим, у нас есть две функции fooи barс типами

foo  :  интервал  ->  интервал бар  :  интервал  ->  интервал

То есть обе функции принимают целое число и возвращают другое целое число. Затем мы можем последовательно применять функции следующим образом:

foo  ( бар  x )

Где результат - это результат fooприменения к результату barприменения x.

Но предположим, что мы отлаживаем нашу программу и хотим добавить сообщения журнала в fooи bar. Итак, мы меняем типы так:

foo  :  int  ->  int  *  строка bar  :  int  ->  int  *  строка

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

К сожалению, это означает, что мы больше не можем составлять fooи bar, поскольку их тип ввода intнесовместим с их типом вывода int * string. И хотя мы снова можем получить возможность компоновки, изменив типы каждой функции, для int * string -> int * stringэтого нам потребуется добавить шаблонный код к каждой функции для извлечения целого числа из кортежа, что станет утомительным по мере увеличения числа таких функций.

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

привязка  :  int  *  строка  ->  ( int  ->  int  *  строка )  ->  int  *  строка

bindпринимает целочисленный и строковый кортеж, а затем принимает функцию (например foo), которая преобразует целое число в целочисленный и строковый кортеж. Его вывод представляет собой целочисленный и строковый кортеж, который является результатом применения входной функции к целому числу внутри входного целого числа и строкового кортежа. Таким образом, нам нужно только написать шаблонный код для однократного извлечения целого числа из кортежа в формате bind.

Теперь мы восстановили возможность компоновки. Например:

bind  ( bind  ( x , s )  bar )  foo

Где (x,s)целочисленный и строковый кортеж.

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

( >> = )  :  int  *  строка  ->  ( int  ->  int  *  строка )  ->  int  *  строка

Так что t >>= fэто то же самое, что и bind t f.

Тогда приведенный выше пример становится:

(( x , s )  >> =  bar )  >> =  foo

Наконец, было бы неплохо не писать (x, "")каждый раз, когда мы хотим создать пустое сообщение журнала, где ""- пустая строка. Итак, давайте определим новую функцию:

возврат  :  int  ->  int  *  строка

Что оборачивается xв кортеж, описанный выше.

Теперь у нас есть хороший конвейер для регистрации сообщений:

(( возврат  x )  >> =  бар )  >> =  foo

Это позволяет нам более легко регистрировать последствия barи fooвключение x.

int * stringаналогично монадическому значению . bindи returnаналогичны соответствующим одноименным функциям. В самом деле, int * string, bindи returnобразуют монаду.

См. Также [ править ]

Альтернативы для моделирования вычислений:

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

Связанные концепции дизайна:

• Аспектно-ориентированное программирование подчеркивает выделение вспомогательного бухгалтерского кода для улучшения модульности и простоты.
• Инверсия управления - это абстрактный принцип вызова определенных функций из всеобъемлющей структуры.
• Классы типов - это особая языковая функция, используемая для реализации монад и других структур в Haskell.
• Шаблон декоратора является более конкретным, одноранговым способом для достижения подобных преимуществ в объектно-ориентированном программировании

Обобщения монад:

• Аппликативные функторы обобщают монады, сохраняя только единицу и законы, относящиеся к ней, к карте
• Стрелки используют дополнительную структуру для объединения простых функций и монад в единый интерфейс.
• Трансформаторы монад воздействуют на отдельные монады, чтобы объединить их модульно

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

В Wikibook Haskell есть страница по теме: Понимание монад

Ссылки на HaskellWiki:

• " All About Monads " (первоначально Джефф Ньюберн) - всестороннее обсуждение всех общих монад и того, как они работают в Haskell; включает аналогию с «механизированной сборочной линией».
• " Typeclassopedia " (первоначально Брент Йорги) - подробное описание того, как взаимосвязаны ведущие классы типов в Haskell, включая монады.

Учебники:

• « Пригоршня монад » (от онлайна Haskell учебник научит вас в Haskell ради Добра! - глава , введение монады от начальной точки функтора и аппликативных функторных классов типов, включая примеры.
• « Еще на несколько монад » - вторая глава, объясняющая более подробную информацию и примеры, включая Probabilityмонаду для цепей Маркова .
• " Функторы, аппликативные, И монады в картинках (Адития Bhargava) - быстрое, с чувством юмора, и визуальный учебник по монадам.

Интересные кейсы:

• « Каналы UNIX как монады ввода-вывода » (Олег Киселев) - короткое эссе, объясняющее, как каналы Unix фактически монадичны.
• Pro Scala: монадические шаблоны дизайна для Интернета (от Грегори Мередита) - неопубликованная полноразмерная рукопись о том, как улучшить многие аспекты веб-разработки на Scala с помощью монад.