Вариант/может быть, любой и будущие монады в JavaScript, Python, Ruby, Swift и Scala

В этом руководстве по монадам дается краткое объяснение монад и показано, как реализовать наиболее полезные из них на пяти разных языках программирования — если вы ищете монады в JavaScript, монады в Python, монады в Ruby, монады в Swift и/или монады. в Scala или сравнивать любые реализации, вы читаете нужную статью!

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

Вот что я расскажу ниже:

• Введение в теорию категорий
• Определение монады
• Реализации монады Option («Может быть»), монады Someone и монады Future, а также пример программы, использующей их, в JavaScript, Python, Ruby, Swift и Scala.

Давайте начнем! Наша первая остановка — теория категорий, которая является основой для монад.

Введение в теорию категорий

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

Итак, есть три основных понятия, которые определяют категорию:

1. Тип именно такой, каким мы его видим в статически типизированных языках. Примеры: Int , String , Dog , Cat и т. д.
2. Функции соединяют два типа. Поэтому их можно представить как стрелку от одного типа к другому или к самим себе. Функцию $f$ из типа $T$ в тип $U$ можно обозначить как $f: T \to U$. Вы можете думать об этом как о функции языка программирования, которая принимает аргумент типа $T$ и возвращает значение типа $U$.
3. Композиция — это операция, обозначаемая оператором $\cdot$, которая строит новые функции из существующих. В категории всегда гарантируется, что для любых функций $f: T \to U$ и $g: U \to V$ существует единственная функция $h: T \to V$. Эта функция обозначается как $f \cdot g$. Операция эффективно отображает пару функций на другую функцию. В языках программирования эта операция, конечно, возможна всегда. Например, если у вас есть функция, возвращающая длину строки —$strlen: String \to Int$ — и функция, сообщающая, является ли число четным —$even: Int \to Boolean$, — тогда вы можете создать функция $even{\_}strlen: String \to Boolean$, которая сообщает, является ли длина String четной. В этом случае $even{\_}strlen = even \cdot strlen$. Состав предполагает две особенности:
   1. Ассоциативность: $f \cdot g \cdot h = (f \cdot g) \cdot h = f \cdot (g \cdot h)$
   2. Существование тождественной функции: $\forall T: \exists f: T \to T$, или, проще говоря, для каждого типа $T$ существует функция, которая отображает $T$ в себя.

Итак, давайте рассмотрим простую категорию.

Дополнительное примечание: мы предполагаем, что Int , String и все другие типы здесь гарантированно не будут нулевыми, т. е. нулевого значения не существует.

Примечание 2. На самом деле это только часть категории, но это все, что нам нужно для нашего обсуждения, потому что в нем есть все основные части, которые нам нужны, и таким образом диаграмма менее загромождена. Реальная категория также будет иметь все составные функции, такие как $roundToString: Double \to String = intToString \cdot round$, чтобы удовлетворить пункту композиции категорий.

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

Было бы неплохо, если бы весь наш код просто работал на таком уровне стабильности? Абсолютно! Но как насчет ввода-вывода, например? Мы определенно не можем жить без него. Вот где монадные решения приходят на помощь: они изолируют все нестабильные операции в очень маленькие и очень хорошо проверенные фрагменты кода, после чего вы можете использовать стабильные вычисления во всем своем приложении!

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

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

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

1. Заполните его значениями типов из категории $A$, таких как String , Int , Double и т. д. (зеленые прямоугольники на диаграмме ниже)
2. Когда у нас есть эти значения, мы все еще не можем сделать с ними ничего значимого, поэтому нам нужен способ взять каждую функцию $f: T \to U$ из $A$ и создать функцию $g: M[T] \to M [U]$ (синие стрелки на диаграмме ниже). Когда у нас есть эти функции, мы можем делать со значениями в категории $M[A]$ все, что мы могли делать в категории $A$.
3. Теперь, когда у нас есть совершенно новая категория $M[A]$, появляется новый класс функций с сигнатурой $h: T \to M[U]$ (красные стрелки на диаграмме ниже). Они появляются в результате продвижения значений на первом этапе как части нашей кодовой базы, т. е. мы пишем их по мере необходимости; это основные моменты, которые отличают работу с $M[A]$ от работы с $A$. Последним шагом будет заставить эти функции хорошо работать с типами в $M[A]$, т. е. получить возможность вывести функцию $m: M[T] \to M[U]$ из $h: T \ в М[U]$

Итак, давайте начнем с определения двух способов преобразования значений типов $A$ в значения типов $M[A]$: одна функция без побочных эффектов и одна с побочными эффектами.

1. Первый называется $pure$ и определяется для каждого значения стабильной категории: $pure: T \to M[T]$. Результирующие значения $M[T]$ не будут иметь побочных эффектов, поэтому эта функция называется $pure$. Например, для монады ввода-вывода $pure$ немедленно вернет какое-то значение без возможности ошибки.
2. Второй называется $constructor$ и, в отличие от $pure$, возвращает $M[T]$ с некоторыми побочными эффектами. Примером такого $конструктора$ для монады асинхронного ввода-вывода может быть функция, которая извлекает некоторые данные из Интернета и возвращает их в виде String . В этом случае значение, возвращаемое $constructor$, будет иметь тип $M[String]$.

Теперь, когда у нас есть два способа продвижения значений в $M[A]$, вам как программисту решать, какую функцию использовать, в зависимости от целей вашей программы. Давайте рассмотрим пример: вы хотите получить HTML-страницу, например https://www.toptal.com/javascript/option-maybe-either-future-monads-js, и для этого вы создаете функцию $fetch$. Так как что-то может пойти не так во время выборки — сбой сети и т. д. — вы будете использовать $M[String]$ в качестве возвращаемого значения этой функции. Таким образом, это будет выглядеть примерно так: $fetch: String \to M[String]$ и где-то в теле функции мы будем использовать $constructor$ для $M$.

Теперь давайте предположим, что мы делаем фиктивную функцию для тестирования: $fetchMock: String \to M[String]$. Он по-прежнему имеет ту же сигнатуру, но на этот раз мы просто вставляем результирующую HTML-страницу внутрь тела $fetchMock$, не выполняя никаких нестабильных сетевых операций. Так что в этом случае мы просто используем $pure$ в реализации $fetchMock$.

В качестве следующего шага нам нужна функция, которая безопасно переводит любую произвольную функцию $f$ из категории $A$ в $M[A]$ (синие стрелки на диаграмме). Эта функция называется $map: (T \to U) \to (M[T] \to M[U])$.

Теперь у нас есть категория (которая может иметь побочные эффекты, если мы используем $constructor$), в которой также есть все функции из категории стабильных, то есть они стабильны и в $M[A]$. Вы могли заметить, что мы явно ввели еще один класс функций, таких как $f: T \to M[U]$. Например, $pure$ и $constructor$ являются примерами таких функций для $U = T$, но очевидно, что их может быть больше, например, если бы мы использовали $pure$, а затем $map$. Итак, в общем случае нам нужен способ работы с произвольными функциями в форме $f: T \to M[U]$.

Если мы хотим создать новую функцию на основе $f$, которую можно было бы применить к $M[T]$, мы могли бы попробовать использовать $map$. Но это приведет нас к функции $g: M[T] \to M[M[U]]$, что нехорошо, поскольку мы не хотим иметь еще одну категорию $M[M[A]]$. Чтобы решить эту проблему, мы вводим последнюю функцию: $flatMap: (T \to M[U]) \to (M[T] \to M[U])$.

Но зачем нам это? Предположим, мы прошли шаг 2, т. е. у нас есть $pure$, $constructor$ и $map$. Допустим, мы хотим получить HTML-страницу с сайта toptal.com, затем просканировать все URL-адреса и получить их. Я бы сделал функцию $fetch: String \to M[String]$, которая извлекает только один URL-адрес и возвращает HTML-страницу.

Затем я применил бы эту функцию к URL-адресу и получил бы страницу от toptal.com, которая имеет вид $x: M[String]$. Теперь я выполняю некоторое преобразование $x$ и, наконец, получаю некоторый URL-адрес $u: M[String]$. Я хочу применить к нему функцию $fetch$, но не могу, потому что она принимает тип $String$, а не $M[String]$. Вот почему нам нужен $flatMap$ для преобразования $fetch: String \to M[String]$ в $m_fetch: M[String] \to M[String]$.

Теперь, когда мы выполнили все три шага, мы можем составить любые преобразования значений, которые нам нужны. Например, если у вас есть значение $x$ типа $M[T]$ и $f: T \to U$, вы можете использовать $map$, чтобы применить $f$ к значению $x$ и получить значение $y$. типа $M[U]$. Таким образом, любое преобразование значений может быть выполнено на 100% без ошибок, если реализации $pure$, $constructor$, $map$ и $flatMap$ не содержат ошибок.

Таким образом, вместо того, чтобы иметь дело с некоторыми неприятными эффектами каждый раз, когда вы сталкиваетесь с ними в своей кодовой базе, вам просто нужно убедиться, что только эти четыре функции реализованы правильно. В конце программы вы получите всего один $M[X]$, из которого можно безопасно развернуть значение $X$ и обработать все случаи ошибок.

Вот что такое монада: вещь, которая реализует $pure$, $map$ и $flatMap$. (На самом деле $map$ может быть производным от $pure$ и $flatMap$, но это очень полезная и широко распространенная функция, поэтому я не исключил ее из определения.)

Монада Option, также известная как монада Maybe.

Хорошо, давайте углубимся в практическую реализацию и использование монад. Первая действительно полезная монада — это Option монада. Если вы переходите с классических языков программирования, вы, вероятно, сталкивались со многими сбоями из-за печально известной ошибки нулевого указателя. Тони Хоар, изобретатель нуля, называет это изобретение «ошибкой на миллиард долларов»:

Это привело к бесчисленным ошибкам, уязвимостям и системным сбоям, которые, вероятно, причинили миллиарды долларов боли и ущерба за последние сорок лет.

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

 class Monad { // pure :: a -> M a pure = () => { throw "pure method needs to be implemented" } // flatMap :: # M a -> (a -> M b) -> M b flatMap = (x) => { throw "flatMap method needs to be implemented" } // map :: # M a -> (a -> b) -> M b map = f => this.flatMap(x => new this.pure(f(x))) } export class Option extends Monad { // pure :: a -> Option a pure = (value) => { if ((value === null) || (value === undefined)) { return none; } return new Some(value) } // flatMap :: # Option a -> (a -> Option b) -> Option b flatMap = f => this.constructor.name === 'None' ? none : f(this.value) // equals :: # M a -> M a -> boolean equals = (x) => this.toString() === x.toString() } class None extends Option { toString() { return 'None'; } } // Cached None class value export const none = new None() Option.pure = none.pure export class Some extends Option { constructor(value) { super(); this.value = value; } toString() { return `Some(${this.value})` } }

 class Monad: # pure :: a -> M a @staticmethod def pure(x): raise Exception("pure method needs to be implemented") # flat_map :: # M a -> (a -> M b) -> M b def flat_map(self, f): raise Exception("flat_map method needs to be implemented") # map :: # M a -> (a -> b) -> M b def map(self, f): return self.flat_map(lambda x: self.pure(f(x))) class Option(Monad): # pure :: a -> Option a @staticmethod def pure(x): return Some(x) # flat_map :: # Option a -> (a -> Option b) -> Option b def flat_map(self, f): if self.defined: return f(self.value) else: return nil class Some(Option): def __init__(self, value): self.value = value self.defined = True class Nil(Option): def __init__(self): self.value = None self.defined = False nil = Nil()

 class Monad # pure :: a -> M a def self.pure(x) raise StandardError("pure method needs to be implemented") end # pure :: a -> M a def pure(x) self.class.pure(x) end def flat_map(f) raise StandardError("flat_map method needs to be implemented") end # map :: # M a -> (a -> b) -> M b def map(f) flat_map(-> (x) { pure(f.call(x)) }) end end class Option < Monad attr_accessor :defined, :value # pure :: a -> Option a def self.pure(x) Some.new(x) end # pure :: a -> Option a def pure(x) Some.new(x) end # flat_map :: # Option a -> (a -> Option b) -> Option b def flat_map(f) if defined f.call(value) else $none end end end class Some < Option def initialize(value) @value = value @defined = true end end class None < Option def initialize() @defined = false end end $none = None.new()

 import Foundation enum Maybe<A> { case None case Some(A) static func pure<B>(_ value: B) -> Maybe<B> { return .Some(value) } func flatMap<B>(_ f: (A) -> Maybe<B>) -> Maybe<B> { switch self { case .None: return .None case .Some(let value): return f(value) } } func map<B>(f: (A) -> B) -> Maybe<B> { return self.flatMap { type(of: self).pure(f($0)) } } }

 import language.higherKinds trait Monad[M[_]] { def pure[A](a: A): M[A] def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B] def map[A, B](ma: M[A])(f: A => B): M[B] = flatMap(ma)(x => pure(f(x))) } object Monad { def apply[F[_]](implicit M: Monad[F]): Monad[F] = M implicit val myOptionMonad = new Monad[MyOption] { def pure[A](a: A) = MySome(a) def flatMap[A, B](ma: MyOption[A])(f: A => MyOption[B]): MyOption[B] = ma match { case MyNone => MyNone case MySome(a) => f(a) } } } sealed trait MyOption[+A] { def flatMap[B](f: A => MyOption[B]): MyOption[B] = Monad[MyOption].flatMap(this)(f) def map[B](f: A => B): MyOption[B] = Monad[MyOption].map(this)(f) } case object MyNone extends MyOption[Nothing] case class MySome[A](x: A) extends MyOption[A]

Мы начнем с реализации класса Monad , который будет основой для всех наших реализаций монад. Иметь этот класс очень удобно, потому что, реализовав всего два его метода — pure и flatMap — для конкретной монады, вы получите много методов бесплатно (в наших примерах мы ограничиваемся просто методом map , но вообще их много другие полезные методы, такие как sequence и traverse для работы с массивами Monad s).

Мы можем выразить map как композицию pure и flatMap . Вы можете видеть из подписи flatMap $flatMap: (T \to M[U]) \to (M[T] \to M[U])$, что это действительно близко к $map: (T \to U) \ в (M[T] \to M[U])$. Разница заключается в том, что в середине есть дополнительный $M$, но мы можем использовать pure функцию для преобразования $U$ в $M[U]$. Таким образом, мы выражаем map в терминах flatMap и pure .

Это хорошо работает для Scala, потому что у него продвинутая система типов. Он также хорошо работает для JS, Python и Ruby, поскольку они динамически типизированы. К сожалению, это не работает для Swift, потому что он статически типизирован и не имеет расширенных функций типов, таких как типы более высокого типа, поэтому для Swift нам придется реализовать map для каждой монады.

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

Теперь, когда у нас есть базовый класс Monad , давайте перейдем к реализации нашей монады Option. Как упоминалось ранее, основная идея заключается в том, что Option либо содержит какое-то значение (называемое Some ), либо вообще не содержит никакого значения ( None ).

pure метод просто повышает значение до Some , в то время как метод flatMap проверяет текущее значение Option — если это None , то он возвращает None , а если это Some с базовым значением, он извлекает базовое значение, применяет f() к это и возвращает результат.

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

Либо Монада

Давайте погрузимся во вторую монаду: Либо. Это в основном то же самое, что и Option монада, но с Some , называемым Right и None , называемым Left . Но на этот раз Left также может иметь базовое значение.

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

 import Monad from './monad'; export class Either extends Monad { // pure :: a -> Either a pure = (value) => { return new Right(value) } // flatMap :: # Either a -> (a -> Either b) -> Either b flatMap = f => this.isLeft() ? this : f(this.value) isLeft = () => this.constructor.name === 'Left' } export class Left extends Either { constructor(value) { super(); this.value = value; } toString() { return `Left(${this.value})` } } export class Right extends Either { constructor(value) { super(); this.value = value; } toString() { return `Right(${this.value})` } } // attempt :: (() -> a) -> M a Either.attempt = f => { try { return new Right(f()) } catch(e) { return new Left(e) } } Either.pure = (new Left(null)).pure

 from monad import Monad class Either(Monad): # pure :: a -> Either a @staticmethod def pure(value): return Right(value) # flat_map :: # Either a -> (a -> Either b) -> Either b def flat_map(self, f): if self.is_left: return self else: return f(self.value) class Left(Either): def __init__(self, value): self.value = value self.is_left = True class Right(Either): def __init__(self, value): self.value = value self.is_left = False

 require_relative './monad' class Either < Monad attr_accessor :is_left, :value # pure :: a -> Either a def self.pure(value) Right.new(value) end # pure :: a -> Either a def pure(value) self.class.pure(value) end # flat_map :: # Either a -> (a -> Either b) -> Either b def flat_map(f) if is_left self else f.call(value) end end end class Left < Either def initialize(value) @value = value @is_left = true end end class Right < Either def initialize(value) @value = value @is_left = false end end

 import Foundation enum Either<A, B> { case Left(A) case Right(B) static func pure<C>(_ value: C) -> Either<A, C> { return Either<A, C>.Right(value) } func flatMap<D>(_ f: (B) -> Either<A, D>) -> Either<A, D> { switch self { case .Left(let x): return Either<A, D>.Left(x) case .Right(let x): return f(x) } } func map<C>(f: (B) -> C) -> Either<A, C> { return self.flatMap { Either<A, C>.pure(f($0)) } } }

 package monad sealed trait MyEither[+E, +A] { def flatMap[EE >: E, B](f: A => MyEither[EE, B]): MyEither[EE, B] = Monad[MyEither[EE, ?]].flatMap(this)(f) def map[EE >: E, B](f: A => B): MyEither[EE, B] = Monad[MyEither[EE, ?]].map(this)(f) } case class MyLeft[E](e: E) extends MyEither[E, Nothing] case class MyRight[A](a: A) extends MyEither[Nothing, A] // ... implicit def myEitherMonad[E] = new Monad[MyEither[E, ?]] { def pure[A](a: A) = MyRight(a) def flatMap[A, B](ma: MyEither[E, A])(f: A => MyEither[E, B]): MyEither[E, B] = ma match { case MyLeft(a) => MyLeft(a) case MyRight(b) => f(b) } }

Также обратите внимание, что исключения легко перехватывать: все, что вам нужно сделать, это сопоставить Left to Right . (Хотя для краткости мы не делаем этого в наших примерах.)

Монада будущего

Давайте исследуем последнюю монаду, которая нам нужна: монаду Future. Монада Future — это в основном контейнер для значения, которое либо доступно сейчас, либо будет доступно в ближайшем будущем. Вы можете создавать цепочки Futures с map и flatMap , которые будут ждать, пока значение Future будет разрешено, прежде чем выполнять следующий фрагмент кода, который зависит от значения, которое будет разрешено первым. Это очень похоже на концепцию промисов в JS.

Наша цель сейчас — объединить существующие асинхронные API на разных языках в одну согласованную базу. Оказывается, самый простой подход к проектированию — использование обратных вызовов в $constructor$.

Хотя дизайн обратного вызова представил проблему ада обратных вызовов в JavaScript и других языках, для нас это не будет проблемой, поскольку мы используем монады. На самом деле объект Promise — основа JavaScript-решения для ада обратных вызовов — сам по себе является монадой!

А как насчет конструктора монады Future? Есть такая подпись:

constructor :: ((Either err a -> void) -> void) -> Future (Either err a)

Давайте разделим его на части. Во-первых, давайте определим:

type Callback = Either err a -> void

Таким образом, Callback — это функция, которая принимает в качестве аргумента либо ошибку, либо разрешенное значение и ничего не возвращает. Теперь наша подпись выглядит так:

constructor :: (Callback -> void) -> Future (Either err a)

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

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

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

Основной процесс таков: вы запускаете асинхронное вычисление, указанное в качестве аргумента конструктора, и указываете его обратный вызов на наш внутренний метод обратного вызова. А пока вы можете подписаться на монаду Future и поставить свои callback-функции в очередь. После завершения вычисления внутренний метод обратного вызова вызывает все обратные вызовы в очереди. Если вы знакомы с реактивными расширениями (RxJS, RxSwift и т. д.), они используют очень похожий подход к асинхронной обработке.

Публичный API монады Future состоит из pure , map и flatMap , как и в предыдущих монадах. Нам также понадобится пара удобных методов:

1. async , который принимает функцию синхронной блокировки и выполняет ее в отдельном потоке, и
2. traverse , который принимает массив значений и функцию, которая сопоставляет значение с Future и возвращает Future массива разрешенных значений.

Давайте посмотрим, как это работает:

 import Monad from './monad'; import { Either, Left, Right } from './either'; import { none, Some } from './option'; export class Future extends Monad { // constructor :: ((Either err a -> void) -> void) -> Future (Either err a) constructor(f) { super(); this.subscribers = []; this.cache = none; f(this.callback) } // callback :: Either err a -> void callback = (value) => { this.cache = new Some(value) while (this.subscribers.length) { const subscriber = this.subscribers.shift(); subscriber(value) } } // subscribe :: (Either err a -> void) -> void subscribe = (subscriber) => (this.cache === none ? this.subscribers.push(subscriber) : subscriber(this.cache.value)) toPromise = () => new Promise( (resolve, reject) => this.subscribe(val => val.isLeft() ? reject(val.value) : resolve(val.value)) ) // pure :: a -> Future a pure = Future.pure // flatMap :: (a -> Future b) -> Future b flatMap = f => new Future( cb => this.subscribe(value => value.isLeft() ? cb(value) : f(value.value).subscribe(cb)) ) } Future.async = (nodeFunction, ...args) => { return new Future(cb => nodeFunction(...args, (err, data) => err ? cb(new Left(err)) : cb(new Right(data))) ); } Future.pure = value => new Future(cb => cb(Either.pure(value))) // traverse :: [a] -> (a -> Future b) -> Future [b] Future.traverse = list => f => list.reduce( (acc, elem) => acc.flatMap(values => f(elem).map(value => [...values, value])), Future.pure([]) )

 from monad import Monad from option import nil, Some from either import Either, Left, Right from functools import reduce import threading class Future(Monad): # __init__ :: ((Either err a -> void) -> void) -> Future (Either err a) def __init__(self, f): self.subscribers = [] self.cache = nil self.semaphore = threading.BoundedSemaphore(1) f(self.callback) # pure :: a -> Future a @staticmethod def pure(value): return Future(lambda cb: cb(Either.pure(value))) def exec(f, cb): try: data = f() cb(Right(data)) except Exception as err: cb(Left(err)) def exec_on_thread(f, cb): t = threading.Thread(target=Future.exec, args=[f, cb]) t.start() def async(f): return Future(lambda cb: Future.exec_on_thread(f, cb)) # flat_map :: (a -> Future b) -> Future b def flat_map(self, f): return Future( lambda cb: self.subscribe( lambda value: cb(value) if (value.is_left) else f(value.value).subscribe(cb) ) ) # traverse :: [a] -> (a -> Future b) -> Future [b] def traverse(arr): return lambda f: reduce( lambda acc, elem: acc.flat_map( lambda values: f(elem).map( lambda value: values + [value] ) ), arr, Future.pure([])) # callback :: Either err a -> void def callback(self, value): self.semaphore.acquire() self.cache = Some(value) while (len(self.subscribers) > 0): sub = self.subscribers.pop(0) t = threading.Thread(target=sub, args=[value]) t.start() self.semaphore.release() # subscribe :: (Either err a -> void) -> void def subscribe(self, subscriber): self.semaphore.acquire() if (self.cache.defined): self.semaphore.release() subscriber(self.cache.value) else: self.subscribers.append(subscriber) self.semaphore.release()

 require_relative './monad' require_relative './either' require_relative './option' class Future < Monad attr_accessor :subscribers, :cache, :semaphore # initialize :: ((Either err a -> void) -> void) -> Future (Either err a) def initialize(f) @subscribers = [] @cache = $none @semaphore = Queue.new @semaphore.push(nil) f.call(method(:callback)) end # pure :: a -> Future a def self.pure(value) Future.new(-> (cb) { cb.call(Either.pure(value)) }) end def self.async(f, *args) Future.new(-> (cb) { Thread.new { begin cb.call(Right.new(f.call(*args))) rescue => e cb.call(Left.new(e)) end } }) end # pure :: a -> Future a def pure(value) self.class.pure(value) end # flat_map :: (a -> Future b) -> Future b def flat_map(f) Future.new(-> (cb) { subscribe(-> (value) { if (value.is_left) cb.call(value) else f.call(value.value).subscribe(cb) end }) }) end # traverse :: [a] -> (a -> Future b) -> Future [b] def self.traverse(arr, f) arr.reduce(Future.pure([])) do |acc, elem| acc.flat_map(-> (values) { f.call(elem).map(-> (value) { values + [value] }) }) end end # callback :: Either err a -> void def callback(value) semaphore.pop self.cache = Some.new(value) while (subscribers.count > 0) sub = self.subscribers.shift Thread.new { sub.call(value) } end semaphore.push(nil) end # subscribe :: (Either err a -> void) -> void def subscribe(subscriber) semaphore.pop if (self.cache.defined) semaphore.push(nil) subscriber.call(cache.value) else self.subscribers.push(subscriber) semaphore.push(nil) end end end

 import Foundation let background = DispatchQueue(label: "background", attributes: .concurrent) class Future<Err, A> { typealias Callback = (Either<Err, A>) -> Void var subscribers: Array<Callback> = Array<Callback>() var cache: Maybe<Either<Err, A>> = .None var semaphore = DispatchSemaphore(value: 1) lazy var callback: Callback = { value in self.semaphore.wait() self.cache = .Some(value) while (self.subscribers.count > 0) { let subscriber = self.subscribers.popLast() background.async { subscriber?(value) } } self.semaphore.signal() } init(_ f: @escaping (@escaping Callback) -> Void) { f(self.callback) } func subscribe(_ cb: @escaping Callback) { self.semaphore.wait() switch cache { case .None: subscribers.append(cb) self.semaphore.signal() case .Some(let value): self.semaphore.signal() cb(value) } } static func pure<B>(_ value: B) -> Future<Err, B> { return Future<Err, B> { $0(Either<Err, B>.pure(value)) } } func flatMap<B>(_ f: @escaping (A) -> Future<Err, B>) -> Future<Err, B> { return Future<Err, B> { [weak self] cb in guard let this = self else { return } this.subscribe { value in switch value { case .Left(let err): cb(Either<Err, B>.Left(err)) case .Right(let x): f(x).subscribe(cb) } } } } func map<B>(_ f: @escaping (A) -> B) -> Future<Err, B> { return self.flatMap { Future<Err, B>.pure(f($0)) } } static func traverse<B>(_ list: Array<A>, _ f: @escaping (A) -> Future<Err, B>) -> Future<Err, Array<B>> { return list.reduce(Future<Err, Array<B>>.pure(Array<B>())) { (acc: Future<Err, Array<B>>, elem: A) in return acc.flatMap { elems in return f(elem).map { val in return elems + [val] } } } } }

 package monad import java.util.concurrent.Semaphore class MyFuture[A] { private var subscribers: List[MyEither[Exception, A] => Unit] = List() private var cache: MyOption[MyEither[Exception, A]] = MyNone private val semaphore = new Semaphore(1) def this(f: (MyEither[Exception, A] => Unit) => Unit) { this() f(this.callback _) } def flatMap[B](f: A => MyFuture[B]): MyFuture[B] = Monad[MyFuture].flatMap(this)(f) def map[B](f: A => B): MyFuture[B] = Monad[MyFuture].map(this)(f) def callback(value: MyEither[Exception, A]): Unit = { semaphore.acquire cache = MySome(value) subscribers.foreach { sub => val t = new Thread( new Runnable { def run: Unit = { sub(value) } } ) t.start } subscribers = List() semaphore.release } def subscribe(sub: MyEither[Exception, A] => Unit): Unit = { semaphore.acquire cache match { case MyNone => subscribers = sub :: subscribers semaphore.release case MySome(value) => semaphore.release sub(value) } } } object MyFuture { def async[B, C](f: B => C, arg: B): MyFuture[C] = new MyFuture[C]({ cb => val t = new Thread( new Runnable { def run: Unit = { try { cb(MyRight(f(arg))) } catch { case e: Exception => cb(MyLeft(e)) } } } ) t.start }) def traverse[A, B](list: List[A])(f: A => MyFuture[B]): MyFuture[List[B]] = { list.foldRight(Monad[MyFuture].pure(List[B]())) { (elem, acc) => Monad[MyFuture].flatMap(acc) ({ values => Monad[MyFuture].map(f(elem)) { value => value :: values } }) } } } // ... implicit val myFutureMonad = new Monad[MyFuture] { def pure[A](a: A): MyFuture[A] = new MyFuture[A]({ cb => cb(myEitherMonad[Exception].pure(a)) }) def flatMap[A, B](ma: MyFuture[A])(f: A => MyFuture[B]): MyFuture[B] = new MyFuture[B]({ cb => ma.subscribe(_ match { case MyLeft(e) => cb(MyLeft(e)) case MyRight(a) => f(a).subscribe(cb) }) }) }

Теперь обратите внимание, что общедоступный API Future не содержит никаких низкоуровневых деталей, таких как потоки, семафоры и тому подобное. Все, что вам нужно, это в основном предоставить что-то с обратным вызовом, и все!

Составление программы из монад

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

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

 import { Future } from './future'; import { Either, Left, Right } from './either'; import { readFile } from 'fs'; import https from 'https'; const getResponse = url => new Future(cb => https.get(url, res => { var body = ''; res.on('data', data => body += data); res.on('end', data => cb(new Right(body))); res.on('error', err => cb(new Left(err))) })) const getShortResponse = url => getResponse(url).map(resp => resp.substring(0, 200)) Future .async(readFile, 'resources/urls.txt') .map(data => data.toString().split("\n")) .flatMap(urls => Future.traverse(urls)(getShortResponse)) .map(console.log)

 import http.client import threading import time import os from future import Future from either import Either, Left, Right conn = http.client.HTTPSConnection("en.wikipedia.org") def read_file_sync(uri): base_dir = os.path.dirname(__file__) #<-- absolute dir the script is in path = os.path.join(base_dir, uri) with open(path) as f: return f.read() def fetch_sync(uri): conn.request("GET", uri) r = conn.getresponse() return r.read().decode("utf-8")[:200] def read_file(uri): return Future.async(lambda: read_file_sync(uri)) def fetch(uri): return Future.async(lambda: fetch_sync(uri)) def main(args=None): lines = read_file("../resources/urls.txt").map(lambda res: res.splitlines()) content = lines.flat_map(lambda urls: Future.traverse(urls)(fetch)) output = content.map(lambda res: print("\n".join(res))) if __name__ == "__main__": main()

 require './lib/future' require 'net/http' require 'uri' semaphore = Queue.new def read(uri) Future.async(-> () { File.read(uri) }) end def fetch(url) Future.async(-> () { uri = URI(url) Net::HTTP.get_response(uri).body[0..200] }) end read("resources/urls.txt") .map(-> (x) { x.split("\n") }) .flat_map(-> (urls) { Future.traverse(urls, -> (url) { fetch(url) }) }) .map(-> (res) { puts res; semaphore.push(true) }) semaphore.pop

 import Foundation enum Err: Error { case Some(String) } func readFile(_ path: String) -> Future<Error, String> { return Future<Error, String> { callback in background.async { let url = URL(fileURLWithPath: path) let text = try? String(contentsOf: url) if let res = text { callback(Either<Error, String>.pure(res)) } else { callback(Either<Error, String>.Left(Err.Some("Error reading urls.txt"))) } } } } func fetchUrl(_ url: String) -> Future<Error, String> { return Future<Error, String> { callback in background.async { let url = URL(string: url) let task = URLSession.shared.dataTask(with: url!) {(data, response, error) in if let err = error { callback(Either<Error, String>.Left(err)) return } guard let nonEmptyData = data else { callback(Either<Error, String>.Left(Err.Some("Empty response"))) return } guard let result = String(data: nonEmptyData, encoding: String.Encoding.utf8) else { callback(Either<Error, String>.Left(Err.Some("Cannot decode response"))) return } let index = result.index(result.startIndex, offsetBy: 200) callback(Either<Error, String>.pure(String(result[..<index]))) } task.resume() } } } var result: Any = "" let _ = readFile("\(projectDir)/Resources/urls.txt") .map { data -> [String] in data.components(separatedBy: "\n").filter { (line: String) in !line.isEmpty } }.flatMap { urls in return Future<Error, String>.traverse(urls) { url in return fetchUrl(url) } }.map { responses in print(responses) } RunLoop.main.run()

 import scala.io.Source import java.util.concurrent.Semaphore import monad._ object Main extends App { val semaphore = new Semaphore(0) def readFile(name: String): MyFuture[List[String]] = MyFuture.async[String, List[String]](filename => Source.fromResource(filename).getLines.toList, name) def fetch(url: String): MyFuture[String] = MyFuture.async[String, String]( uri => Source.fromURL(uri).mkString.substring(0, 200), url ) val future = for { urls <- readFile("urls.txt") entries <- MyFuture.traverse(urls)(fetch _) } yield { println(entries) semaphore.release } semaphore.acquire }

There you have it—monad solutions in practice. You can find a repo containing all the code from this article on GitHub.

Overhead: Done. Benefits: Ongoing

For this simple monad-based program, it might look like overkill to use all the code that we wrote before. But that's just the initial setup, and it will stay constant in its size. Imagine that from now on, using monads, you can write a lot of async code, not worrying about threads, race conditions, semaphores, exceptions, or null pointers! Потрясающий!