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

Чтобы узнать о концепции теории категорий, см. Монаду (теорию категорий) .

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

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

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

Обзор

«Для монады m, значение типа m a представляет собой доступ к значению типа a в контексте монады». — К.А. Макканн

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

Монаду можно создать, определив конструктор типа M и две операции:

• return :: a -> M a (часто также называемый unit ), который получает значение типа a и оборачивает его в монадическое значение типа M a, и
• bind :: (M a) -> (a -> M b) -> (M b) (обычно представляется как >>=), который получает монадическое значение M a и функция f который принимает значения базового типа a. Привязать развертки a, применяется f к нему и может обрабатывать результат f как монадическое значение M b.

(Альтернативная, но эквивалентная конструкция с использованием join функция вместо bind оператор можно найти в следующем разделе § Вывод из функторов .)

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

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

Пример: Возможно

Дополнительная информация: Тип опции.

См. Также: Монада (теория категорий) § Возможно, монада

Одним из примеров монады является Maybe тип. Неопределенные нулевые результаты — это особая болевая точка, для решения которой многие процедурные языки не предоставляют специальных инструментов, требующих использования шаблона нулевого объекта или проверок для проверки недопустимых значений в каждой операции для обработки неопределенных значений. Это вызывает ошибки и затрудняет создание надежного программного обеспечения, которое корректно обрабатывает ошибки. Maybe type заставляет программиста иметь дело с этими потенциально неопределенными результатами, явно определяя два состояния результата: Just ⌑result⌑, или Nothing. Например, программист может создавать анализатор, который должен возвращать промежуточный результат или сигнализировать об условии, которое обнаружил анализатор и которое программист также должен обработать. С небольшим количеством дополнительных функциональных специй сверху, это Maybe type преобразуется в полнофункциональную монаду.

В большинстве языков монада Maybe также известна как тип параметра , который представляет собой тип, который отмечает, содержит ли он значение или нет. Обычно они выражаются как некий перечислимый тип . В этом примере Rust мы назовем это Maybe<T> и варианты этого типа могут быть значением универсального типа Tили пустой вариант: Nothing.

// The <T> represents a generic type "T"
enum Maybe<T> {
    Just(T),
    Nothing,
}

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

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

fn divide(x: Decimal, y: Decimal) -> Maybe<Decimal> {
    if y == 0 { return Nothing }
    else { return Just(x / y) }
}
// divide(1.0, 4.0) -> returns Just(0.25)
// divide(3.0, 0.0) -> returns Nothing

Один из таких способов проверить, является ли Maybe содержит значение, следует использовать if заявления.

let m_x = divide(3.14, 0.0); // see divide function above
// The if statement extracts x from m_x if m_x is the Just variant of Maybe
if let Just(x) = m_x {
    println!("answer: ", x)
} else {
    println!("division failed, divide by zero error...")
}

Другие языки могут иметь сопоставление с образцом.

let result = divide(3.0, 2.0);
match result {
    Just(x) => println!("Answer: ", x),
    Nothing => println!("division failed; we'll get 'em next time."),
}

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

fn chainable_division(maybe_x: Maybe<Decimal>, maybe_y: Maybe<Decimal>) -> Maybe<Decimal> {
    match (maybe_x, maybe_y) {
        (Just(x), Just(y)) => { // If both inputs are Just, check for division by zero and divide accordingly
            if y == 0 { return Nothing }
            else { return Just(x / y) }
        },
        _ => return Nothing // Otherwise return Nothing
    }
}
chainable_division(chainable_division(Just(2.0), Just(0.0)), Just(1.0)); // inside chainable_division fails, outside chainable_division returns Nothing

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

// Rust example using ".map". maybe_x is passed through 2 functions that return Maybe<Decimal> and Maybe<String> respectively.
// As with normal function composition the inputs and outputs of functions feeding into each other should match wrapped types. (i.e. the add_one function should return a Maybe<Decimal> which then can be unwrapped to a Decimal for the decimal_to_string function)
let maybe_x: Maybe<Decimal> = Just(1.0)
let maybe_result = maybe_x.map(add_one).map(decimal_to_string)

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

halve :: Int -> Maybe Int
halve x
  | even x = Just (x `div` 2)
  | odd x  = Nothing
 -- This code halves x twice. it evaluates to Nothing if x is not a multiple of 4
halve x >>= halve

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

 chainable_division(mx,my) =   mx >>=  ( λx ->   my >>= (λy -> Just (x / y))   )

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

Монадический тип

Тип ( Maybe)

Работа агрегата

Преобразователь типов ( Just(x))

Операция привязки

Комбинатор для монадических функций ( >>= или .flatMap())

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

Определение

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

• Конструктор типа M , создающий монадический тип MT.
• Преобразователь типов , часто называемый unit или return , который встраивает объект x в монаду:
  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
• связывание по существу ассоциативно :
  ma >>= λx → (f(x) >>= g) ↔ (ma >>= f) >>= g

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

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

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

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

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

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

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

Приложения

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

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

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

История

Термин «монада» в программировании на самом деле восходит к языкам программирования 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 вместо этого называется fmap в Хаскеле.)

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

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

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

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

В качестве характеристической функции соединение также должно удовлетворять трем вариантам законов монады:

(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 образом демонстрирует, как может оказаться полезным получение монады из более простого функтора. Во многих языках структура списка предопределена вместе с некоторыми базовыми функциями, поэтому List конструктор типа и оператор добавления (представленный как ++ для инфиксной записи) считаются уже указанными здесь.

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

unit(x)  =  [x]

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

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

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

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

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

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

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

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

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

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

Техники

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

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

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

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

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

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

add mx my =
    mx >>= (\x ->
        my >>= (\y ->
            return (x + y)))

Однако с помощью do-нотации это можно еще больше свести к очень интуитивно понятной последовательности:

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 }

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

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

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

Операторы

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

add(mx,my)  =  map (+)

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

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

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

(f >=> g)(x)  =  f(x) >>= g

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

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

В свою очередь, приведенное выше показывает значение блока «do» в Haskell:

do
 _p <- f(x)
 _q <- g(_p)
 h(_q)          ↔ ( f >=> g >=> h )(x)

Больше примеров

Идентификационная монада

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

newtype Id T  =  T

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

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

Коллекции

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

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

IO-монада (Haskell)

Как уже упоминалось, чистый код не должен иметь неуправляемых побочных эффектов, но это не мешает программе явно описывать эффекты и управлять ими. Хаскеля Эта идея является центральной в монаде IO , где объект типа IO a можно рассматривать как описание действия, которое должно быть выполнено в мире, возможно, предоставляющее информацию о мире типа a. Действие, не предоставляющее никакой информации о мире, имеет тип IO (), "предоставляя" фиктивное значение (). Когда программист связывает IO значение функции, функция вычисляет следующее действие, которое должно быть выполнено, на основе информации о мире, предоставленной предыдущим действием (ввод от пользователей, файлов и т. д.). Что наиболее важно, поскольку значение монады IO может быть связано только с функцией, которая вычисляет другую монаду 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 справиться с этими задачами, генерируя вспомогательный вывод, который накапливается шаг за шагом.

Чтобы показать, что шаблон монады не ограничивается преимущественно функциональными языками, в этом примере реализуется 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 → T , где E — тип общей среды. Функции монады: $${\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}}$$

Полезны следующие монадические операции: $${\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). Это похоже на монаду среды, за исключением того, что она также возвращает новое состояние и, таким образом, позволяет моделировать изменяемую среду.

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\rightarrow T\times S$, где S — основное состояние. Функция возврата и привязки :

${\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 в функции типа $\left(T\rightarrow R\right)\rightarrow R$. Он используется для моделирования стиля передачи продолжения . Функции возврата и привязки следующие:

${\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}}$

Функция вызова с текущим продолжением определяется следующим образом:

${\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 : 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 образуют монаду.

Вариации

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

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

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

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

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

Свободные монады

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

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

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.
• Двойник unit , называемый здесь counit , извлекает основное значение из комонады:

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(wa) : W T → W (W T)

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

((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

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

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

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

См. также

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

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

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

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

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

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

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

Ссылки на HaskellWiki:

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

Учебники:

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

Интересные случаи:

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