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

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

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

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

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

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

Обзор

«Для монады mзначение типа m aпредставляет доступ к значению типа aв контексте монады». —CA McCann

Монада может быть создана путем определения конструктора типа 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. Это сделано, чтобы избежать путаницы, путем различения случаев, когда переменная несет определенное значение, и тех, где это не так.

data Maybe T  =  Just T or Nothing

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

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

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

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

 add : (Maybe Number, Maybe Number) → Maybe Number
 add(mx,my) = ...
     if mx is Nothing then
         ... Nothing
     else if my is Nothing then
         ... Nothing
     else
         ... Just (x + y)
     end if

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

 >>= : (Maybe T, T → Maybe U) → Maybe U
 (mx >>= f) = ...
     if mx is (Just x) then
         ... f(x)    -- evaluate f(x) and return (possibly undefined) output
     else
         ... Nothing -- pass through an undefined input
     end if

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

 add(mx,my)  =  mx >>= λx -> (my >>= λy -> Just (x + y))

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

 eta : T → Maybe T
 eta(x)  =  Just x

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

trinot : Maybe Boolean → Maybe Boolean
trinot(mp)  =  mp >>= λp -> (eta ∘ not) p

где ∘обозначает композицию функции, а предыдущее определение эквивалентно:

trinot(mp)  =  mp >>= λp -> Just (not p)

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

Определение

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

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

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

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

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

использование

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

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

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

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

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

Приложения

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

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

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

История

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

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

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

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

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

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

Анализ

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

Проверка законов монад

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

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

Law 1:  eta(a) >>= f(x)  ⇔  (Just a) >>= f(x)  ⇔  f(a)

Law 2:  ma >>= eta(x)           ⇔  ma

        if ma is (Just a) then
            eta(a)              ⇔ Just a
        else                        or
            Nothing             ⇔ Nothing
        end if

Law 3:  (ma >>= f(x)) >>= g(y)                       ⇔  ma >>= (f(x) >>= g(y))

        if (ma >>= f(x)) is (Just b) then               if ma is (Just a) then
            g(ma >>= f(x))                                (f(x) >>= g(y)) a
        else                                            else
            Nothing                                         Nothing
        end if                                          end if

                ⇔  if ma is (Just a) and f(a) is (Just b) then      
                       (g ∘ f) a
                   else if ma is (Just a) and f(a) is Nothing then
                       Nothing
                   else
                       Nothing
                   end if

Вывод из функторов

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

map φ : (a → b) → (ma → mb)

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

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

(unit ∘ φ) x ↔ ((map φ) ∘ unit) x

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

join(mma) : M (M T) → M T

Как характеристическая функция, $join$ также должен удовлетворять трем вариациям законов монад:

(join ∘ (map join)) mmma ↔ (join ∘ join) mmma ↔ ma

(join ∘ (map unit)) ma ↔ (join ∘ unit) ma ↔ ma

(join ∘ (map map φ)) mma ↔ ((map φ) ∘ join) mma ↔ mb

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

(map φ) ma ↔ ma >>= (unit ∘ φ)

join(mma) ↔ mma >>= id

ma >>= f ↔ (join ∘ (map f)) ma

Другой пример: Список

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

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

unit(x)  =  [x]

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

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

(map φ) xlist  =  [ φ(x1), φ(x2), ..., φ(xn) ]

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

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

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

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

(xlist >>= f)  =  join ∘ (map f) xlist

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

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

Методы

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

Синтаксический сахар нотация

Хотя открытое использование $связывания$ часто имеет смысл, многие программисты предпочитают синтаксис, имитирующий императивные операторы (называемый нотацией do в Haskell, нотацией выполнения в OCaml , выражениями вычислений в F # и для понимания в 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монада обеспечивает более четкое определение:

add 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()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None

let secure_div = 
  maybe { 
    let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

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

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return(x / y))))

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

do { x <- return v; f x }            ==  do { f v }
do { x <- m; return x }              ==  do { m }
do { y <- do { x <- m; f x }; g y }  ==  do { x <- m; y <- f x; g y }

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

Общий интерфейс

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

Операторы

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

add(mx,my)  =  map (+)

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

add : (Monad Number, Monad Number)  →  Monad Number

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

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

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

(unit >=> g)     ↔  g
(f >=> unit)     ↔  f
(f >=> g) >=> h  ↔  f >=> (g >=> h)

Вариации

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

Аддитивные монады

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

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

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

Бесплатные монады

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

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

data Free f a
  = Pure a
  | Free (f (Free f a))

unit :: a -> Free f a
unit x = Pure x

bind :: Functor f => Free f a -> (a -> Free f b) -> Free f b
bind (Pure x) f = f x
bind (Free x) f = Free (fmap (\y -> bind y f) x)

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

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

Комонады

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

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

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

counit(wa) : W T → T

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

(wa =>> f) : (W U, W U → T) → W T

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

counit ∘ ( (wa =>> f) → wb )  ↔  f(wa) → b
wa =>> counit  ↔  wa
wa ( (=>> f(wx = wa)) → wb (=>> g(wy = wb)) → wc )  ↔  ( wa (=>> f(wx = wa)) → wb ) (=>> g(wy = wb)) → wc

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

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

duplicate(wa) : W T → W (W T)

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

((map duplicate) ∘ duplicate) wa  ↔  (duplicate ∘ duplicate) wa  ↔  wwwa
((map counit) ∘ duplicate)    wa  ↔  (counit ∘ duplicate)    wa  ↔  wa
((map map φ) ∘ duplicate)     wa  ↔  (duplicate ∘ (map φ))   wa  ↔  wwb

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

(map φ) wa    ↔  wa =>> (φ ∘ counit) wx
duplicate wa  ↔  wa =>> wx

wa =>> f(wx)  ↔  ((map f) ∘ duplicate) wa

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

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

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

Еще примеры

Монада идентичности

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

newtype Id T  =  T

unit(x)    =  x
(x >>= f)  =  f(x)

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

Коллекции

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

Коллекция	Свойства моноида
Список	Бесплатно
Конечное мультимножество	Коммутативный
Конечный набор	Коммутативный и идемпотентный
Конечные перестановки	Некоммутативный и идемпотентный

Монада ввода-вывода (Haskell)

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

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

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

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

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

main :: IO ()
main = do
  putStrLn "Hello, world!"
  putStrLn "What is your name, user?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

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

main :: IO ()
main =
  putStrLn "Hello, world!" >>
  putStrLn "What is your name, user?" >> 
  getLine >>= (\name ->
    putStrLn ("Nice to meet you, " ++ name ++ "!"))

Монада писателя (JavaScript)

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

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

const writer = value => [value, []];

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

const unit = value => [value, []];

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

const squared = x => [x * x, [`${x} was squared.`]];
const halved = x => [x / 2, [`${x} was halved.`]];

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

const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};

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

const pipelog = (writer, ...transforms) =>
    transforms.reduce(bind, writer);

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

pipelog(unit(4), squared, halved);
// Resulting writer object = [8, ['4 was squared.', '16 was halved.']]

Монада окружающей среды

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

{\ displaystyle {\ begin {array} {ll} {\ text {return}} \ двоеточие & T \ rightarrow E \ rightarrow T = t \ mapsto e \ mapsto t \\ {\ text {bind}} \ двоеточие & (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}} \ двоеточие & E \ rightarrow E = {\ text {id}} _ {E} \\ {\ text {local}} \ двоеточие & ( 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 ). Это похоже на монаду среды, за исключением того, что она также возвращает новое состояние и, таким образом, позволяет моделировать изменяемую среду.

type State s t = s -> (t, s)

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

-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

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

get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state

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

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}} \ двоеточие & T \ rightarrow S \ rightarrow T \ times S = t \ mapsto s \ mapsto (t, s) \\ {\ text {bind }} \ двоеточие & (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 \ влево (Т \ rightarrow R \ вправо) \ rightarrow R}$

{\ displaystyle {\ begin {array} {ll} {\ text {return}} \ двоеточие & T \ rightarrow \ left (T \ rightarrow R \ right) \ rightarrow R = t \ mapsto f \ mapsto f \, t \\ {\ text {bind}} \ двоеточие & \ 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) \ конец {массив}}}

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

{\ displaystyle {\ text {call / cc}} \ двоеточие \ \ 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 : int -> int
bar : int -> int

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

foo (bar x)

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

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

foo : int -> int * string
bar : int -> int * string

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

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

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

bind : int * string -> (int -> int * string) -> int * string

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

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

bind (bind (x,s) bar) foo

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

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

(>>=) : int * string -> (int -> int * string) -> int * string

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

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

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

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

return : int -> int * string

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

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

((return x) >>= bar) >>= foo

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

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

Смотрите также

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

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

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

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

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

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

Примечания

использованная литература

внешние ссылки

Ссылки на HaskellWiki:

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

Учебники:

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

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

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

Languages

In other projects

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

СОДЕРЖАНИЕ

Обзор

Пример: Может быть

Определение

использование

Приложения

История

Анализ

Проверка законов монад

Вывод из функторов

Другой пример: Список

Методы

Синтаксический сахар нотация

Общий интерфейс

Операторы

Вариации

Аддитивные монады

Бесплатные монады

Комонады

Еще примеры

Монада идентичности

Коллекции

Монада ввода-вывода (Haskell)

Монада писателя (JavaScript)

Монада окружающей среды

Государственные монады

Монада продолжения

Журнал программы

Смотрите также

Примечания

использованная литература

внешние ссылки

Languages

In other projects

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

Обзор

Пример: Может быть

Определение

использование

Приложения

История

Анализ

Проверка законов монад

Вывод из функторов

Другой пример: Список

Методы

Синтаксический сахар .mw-parser-output .vanchor>:target~.vanchor-text{background-color:#b1d2ff} нотация

Общий интерфейс

Операторы

Вариации

Аддитивные монады

Бесплатные монады

Комонады

Еще примеры

Монада идентичности

Коллекции

Монада ввода-вывода (Haskell)

Монада писателя (JavaScript)

Монада окружающей среды

Государственные монады

Монада продолжения

Журнал программы

Смотрите также

Примечания

использованная литература

внешние ссылки

Синтаксический сахар нотация