Option/Maybe, Either, and Future Monads in JavaScript, Python, Ruby, Swift, and Scala
If you’re searching for the holy grail of bug-free code in JavaScript, Python, Ruby, Swift, and/or Scala, look no further! This monad tutorial by Toptal Freelance Functional Programmer Alexey Karasev takes you from category theory to the practical implementations of the Option/Maybe, Either, and Future monads, plus a sample program—in all five languages.
If you’re searching for the holy grail of bug-free code in JavaScript, Python, Ruby, Swift, and/or Scala, look no further! This monad tutorial by Toptal Freelance Functional Programmer Alexey Karasev takes you from category theory to the practical implementations of the Option/Maybe, Either, and Future monads, plus a sample program—in all five languages.
Alexey (MEcon) is skilled in several languages and prefers functional programming, particularly Scala, to lower time wasted hunting bugs.
Expertise
This monad tutorial gives a brief explanation of monads and shows how to implement the most useful ones in five different programming languages—if you’re looking for monads in JavaScript, monads in Python, monads in Ruby, monads in Swift, and/or monads in Scala, or to compare any implementations, you’re reading the right article!
Using these monads you will get rid of a series of bugs like null-pointer exceptions, unhandled exceptions, and race conditions.
This is what I cover below:
- An introduction into category theory
- The definition of a monad
- Implementations of the Option (“Maybe”) monad, Either monad, and Future monad, plus a sample program leveraging them, in JavaScript, Python, Ruby, Swift, and Scala
Let’s get started! Our first stop is category theory, which is the basis for monads.
Introduction to Category Theory
Category theory is a mathematical field that was actively developed in the middle of the 20th century. Now it is the basis of many functional programming concepts including the monad. Let’s take a quick look into some category theory concepts, tuned for software development terminology.
So there are three core concepts that define a category:
-
Type is just as we see it in statically typed languages. Examples:
Int
,String
,Dog
,Cat
, etc. - Functions connect two types. Therefore, they can be represented as an arrow from one type to another type, or to themselves. Function $f$ from type $T$ to type $U$ can be denoted as $f: T \to U$. You can think of it as a programming language function that takes an argument of type $T$ and returns a value of type $U$.
-
Composition is an operation, denoted by the $\cdot$ operator, that builds new functions from existing ones. In a category, it’s always guaranteed for any functions $f: T \to U$ and $g: U \to V$ there exists a unique function $h: T \to V$. This function is denoted as $f \cdot g$. The operation effectively maps a pair of functions to another function. In programming languages, this operation is, of course, always possible. For instance, if you have a function that returns a length of a string —$strlen: String \to Int$—and a function that tells if the number is even —$even: Int \to Boolean$—then you can make a function $even{\_}strlen: String \to Boolean$ which tells if the length of the
String
is even. In this case $even{\_}strlen = even \cdot strlen$. Composition implies two features:- Associativity: $f \cdot g \cdot h = (f \cdot g) \cdot h = f \cdot (g \cdot h)$
- The existence of an identity function: $\forall T: \exists f: T \to T$, or in plain English, for every type $T$ there exists a function that maps $T$ to itself.
So let’s take a look at a simple category.
Side note: We’re assuming that Int
, String
and all other types here are guaranteed to be non-null, i.e., the null value does not exist.
Side note 2: This is actually only part of a category, but that is all we want for our discussion, because it has all the essential parts we need and the diagram is less cluttered this way. The real category would also have all composed functions like $roundToString: Double \to String = intToString \cdot round$, to satisfy the composition clause of categories.
You might notice that functions in this category are super simple. In fact it’s almost impossible to have a bug in these functions. There are no nulls, no exceptions, just the arithmetic and working with memory. So the only bad thing that can happen is processor or memory failure—in which case you need to crash the program anyway—but that happens very seldomly.
Wouldn’t it be nice if all our code just worked at this level of stability? Absolutely! But what about I/O, for example? We definitely can’t live without it. Here is where monad solutions come to the rescue: They isolate all unstable operations into super-small and very well-audited pieces of code—then you can use stable calculations in your whole app!
Enter Monads
Let’s call unstable behavior like I/O a side effect. Now we want to be able to work with all our previously defined functions like length
and types like String
in a stable way in the presence of this side effect.
So let’s start with an empty category $M[A]$ and make it into a category that will have values with one particular type of side effect and also values with no side effects. Let’s assume we’ve defined this category and it’s empty. Right now there’s nothing useful we can do with it, so to make it useful, we’ll follow these three steps:
- Fill it with values of the types from category $A$, like
String
,Int
,Double
, etc. (green boxes in the diagram below) - Once we have these values, we still cannot do anything meaningful with them, so we need a way to take each function $f: T \to U$ from $A$ and create a function $g: M[T] \to M[U]$ (blue arrows in the diagram below). Once we have these functions, we can do everything with the values in category $M[A]$ that we were able to do in category $A$.
- Now that we have a brand new $M[A]$ category, a new class of functions emerge with signature $h: T \to M[U]$ (red arrows in the diagram below). They emerge as a result of promoting values in step one as part of our codebase, i.e., we write them as needed; these are the main things that will differentiate working with $M[A]$ versus working with $A$. The final step will be to make these functions work well on types in $M[A]$ as well, i.e., being able to derive function $m: M[T] \to M[U]$ from $h: T \to M[U]$
So let’s start off by defining two ways of promoting values of $A$ types to values of $M[A]$ types: one function with no side effects and one with side effects.
- The first is called $pure$ and is defined for each value of a stable category: $pure: T \to M[T]$. The resulting $M[T]$ values won’t have any side effects, hence this function is called $pure$. E.g., for an I/O monad, $pure$ will return some value immediately with no possibility of failure.
- The second is called $constructor$ and, unlike $pure$, returns $M[T]$ with some side effects. An example of such a $constructor$ for an async I/O monad could be a function that fetches some data from the web and returns it as a
String
. The value returned by $constructor$ will have type $M[String]$ in this case.
Now that we have two ways of promoting values into $M[A]$, it’s up to you as a programmer to choose which function to use, depending on your program goals. Let’s consider an example here: You want to fetch an HTML page like https://www.toptal.com/javascript/option-maybe-either-future-monads-js and for this you make a function $fetch$. Since anything could go wrong while fetching it—think network failures, etc.—you’ll use $M[String]$ as the return type of this function. So it will look something like $fetch: String \to M[String]$ and somewhere in the function body there we will use $constructor$ for $M$.
Now let’s assume we make a mock function for testing: $fetchMock: String \to M[String]$. It still has the same signature, but this time we just inject the resulting HTML page inside the body of $fetchMock$ without doing any unstable network operations. So in this case we just use $pure$ in the implementation of $fetchMock$.
As the next step, we need a function that safely promotes any arbitrary function $f$ from the category $A$ to $M[A]$ (blue arrows in a diagram). This function is called $map: (T \to U) \to (M[T] \to M[U])$.
Now we have a category (which can have side effects if we use $constructor$), which also has all functions from the stable category, meaning they are stable in $M[A]$ as well. You might notice that we explicitly introduced another class of functions like $f: T \to M[U]$. E.g., $pure$ and $constructor$ are examples of such functions for $U = T$, but there obviously could be more, like if we were to use $pure$ and then $map$. So, generally, we need a way to deal with arbitrary functions in the form $f: T \to M[U]$.
If we want to make a new function based on $f$ that could be applied to $M[T]$, we could try to use $map$. But that will bring us to function $g: M[T] \to M[M[U]]$, which is no good since we don’t want to have one more category $M[M[A]]$. To deal with this problem, we introduce one last function: $flatMap: (T \to M[U]) \to (M[T] \to M[U])$.
But why would we want to do that? Let’s assume we’re after step 2, i.e., we have $pure$, $constructor$, and $map$. Say we want to grab an HTML page from toptal.com, then scan all the URLs there as well as fetch them. I’d make a function $fetch: String \to M[String]$ that fetches just one URL and returns an HTML page.
Then I’d apply this function to a URL and get a page from toptal.com, which is $x: M[String]$. Now, I do some transformation on $x$ and finally arrive at some URL $u: M[String]$. I want to apply function $fetch$ to it, but I can’t, because it takes type $String$, not $M[String]$. That’s why we need $flatMap$ to convert $fetch: String \to M[String]$ to $m_fetch: M[String] \to M[String]$.
Now that we have completed all three steps, we can actually compose any value transformations we need. For instance, if you have value $x$ of type $M[T]$ and $f: T \to U$, you can use $map$ to apply $f$ to value $x$ and get value $y$ of type $M[U]$. That way any transformation of values can be done in a 100 percent bug-free way, as long as the $pure$, $constructor$, $map$ and $flatMap$ implementations are bug-free.
So instead of dealing with some nasty effects each time you encounter them in your codebase, you just need to make sure that only these four functions are implemented correctly. At the end of the program, you will get just one $M[X]$ where you can safely unwrap the value $X$ and handle all error cases.
This is what a monad is : a thing that implements $pure$, $map$, and $flatMap$. (Actually $map$ can be derived from $pure$ and $flatMap$, but it’s very useful and widespread function, so I didn’t omit it from the definition.)
The Option Monad, a.k.a. the Maybe Monad
Okay, let’s dive into the practical implementation and usage of monads. The first really helpful monad is the Option monad. If you’re coming from classic programming languages, you’ve probably encountered many crashes because of the infamous null pointer error. Tony Hoare, the inventor of null, calls this invention “The Billion Dollar Mistake”:
This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.
So let’s try to improve on that. The Option monad either holds some non-null value, or no value. Pretty similar to a null value, but having this monad, we can safely use our well-defined functions without being afraid of the null pointer exception. Let’s take a look at implementations in different languages:
JavaScript—Option Monad/Maybe Monad
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})`
}
}
Python—Option Monad/Maybe Monad
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()
Ruby—Option Monad/Maybe Monad
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()
Swift—Option Monad/Maybe Monad
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)) }
}
}
Scala—Option Monad/Maybe Monad
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]
We start off by implementing a Monad
class that will be the base for all of our monad implementations. Having this class is very handy, because by implementing just two of its methods —pure
and flatMap
—for a specific monad, you will get many methods for free (we limit them to simply the map
method in our examples, but generally there are many other useful methods, like sequence
and traverse
for working with arrays of Monad
s).
We can express map
as composition of pure
and flatMap
. You can see from flatMap
’s signature $flatMap: (T \to M[U]) \to (M[T] \to M[U])$ that it’s really close to $map: (T \to U) \to (M[T] \to M[U])$. The difference is the additional $M$ in the middle, but we can use the pure
function to convert $U$ into $M[U]$. That way we express map
in terms of flatMap
and pure
.
This works well for Scala, because it has an advanced type system. It also works well for JS, Python, and Ruby, because they are dynamically typed. Unfortunately, it doesn’t work for Swift, because it’s statically typed and doesn’t have advanced type features like higher-kinded types, so for Swift we’ll have to implement map
for each monad.
Also note that the Option monad is already a de facto standard for languages like Swift and Scala, so we use slightly different names for our monad implementations.
Now that we have a base Monad
class, let’s get to our Option monad implementations. As previously mentioned, the basic idea is that Option either holds some value (called Some
) or or doesn’t hold any value at all (None
).
The pure
method simply promotes a value to Some
, while the flatMap
method checks the current value of the Option
— if it’s None
then it returns None
, and if it’s Some
with an underlying value , it extracts the underlying value, applies f()
to it and returns a result.
Note that just using these two functions and map
, it’s impossible to get into a null pointer exception—ever. (The problem could potentially arise in our implementation of the flatMap
method, but that’s just a couple of lines in our code that we check once. After that, we just use our Option monad implementation throughout our code in thousands of places and don’t have to fear the null pointer exception at all.)
The Either Monad
Let’s dive into the second monad : Either. This is basically the same as the Option monad, but with Some
called Right
and None
called Left
. But this time, Left
is also allowed to have an underlying value.
We need that because it’s very convenient to express throwing an exception. If an exception occurred, then the value of the Either
will be Left(Exception)
. The flatMap
function doesn’t progress if the value is Left
, which repeats the semantics of throwing exceptions: If an exception happened, we stop further execution.
JavaScript—Either Monad
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
Python—Either Monad
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
Ruby—Either Monad
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
Swift—Either Monad
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)) }
}
}
Scala—Either Monad
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)
}
}
Also note that it’s easy to catch exceptions: All you have to do is map Left
to Right
. (Although, we don’t do it in our examples, for brevity.)
The Future Monad
Let’s explore the last monad that we need: the Future monad. The Future monad is basically a container for a value which is either available now or will be available in the near future. You can make chains of Futures with map
and flatMap
that will wait for the Future value to be resolved before executing the next piece of code that depends on the value being resolved first. This is very similar to concept of Promises in JS.
Our design goal now is to bridge the existing async APIs in different languages to one consistent base. It turns out that the easiest design approach is using callbacks in $constructor$.
While the callback design introduced the callback hell problem in JavaScript and other languages, it will not be a problem for us, since we use monads. In fact, the Promise
object—the basis for JavaScript’s solution to callback hell—is a monad itself!
What about the constructor of the Future monad? Is has this signature:
constructor :: ((Either err a -> void) -> void) -> Future (Either err a)
Let’s split it into pieces. First, let’s define:
type Callback = Either err a -> void
So Callback
is a function which takes either an error or a resolved value as an argument, and returns nothing. Now our signature looks like this:
constructor :: (Callback -> void) -> Future (Either err a)
So we need to supply it a function that returns nothing and triggers a callback as soon as async computation is resolved to either an error or some value. Looks easy enough to make a bridge for any language.
As for the design of the Future monad itself, let’s look at its internal structure. The key idea is to have a cache variable that holds a value if the Future monad is resolved, or holds nothing otherwise. You can subscribe to the Future with a callback which will be immediately triggered if value is resolved, or if not, will put the callback into the subscribers list.
Once the Future is resolved, each callback in this list will be triggered exactly once with the resolved value in a separate thread (or as the next function to be executed in the event loop, in the case of JS.) Note that it’s crucial to carefully use synchronization primitives, otherwise race conditions are possible.
The basic flow is: You start the async computation supplied as the constructor argument, and point its callback to our internal callback method. In the meantime, you can subscribe to the Future monad and put your callbacks into the queue. Once the computation is done, the internal callback method calls all callbacks in the queue. If you’re familiar with Reactive Extensions (RxJS, RxSwift, etc.), they use a very similar approach to async handling.
The public API of the Future monad consists of pure
, map
, and flatMap
, just like in the previous monads. We’ll also need a couple of handy methods:
-
async
, which takes a synchronous blocking function and executes it on a separate thread, and -
traverse
, which takes an array of values and function that maps a value to aFuture
, and returns aFuture
of an array of resolved values
Let’s see how that plays out:
JavaScript—Future Monad
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([])
)
Python—Future Monad
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()
Ruby—Future Monad
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
Swift—Future Monad
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]
}
}
}
}
}
Scala—Future Monad
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)
})
})
}
Now, notice how the public API of Future
doesn’t contain any low-level details like threads, semaphores, or any of that stuff. All you need is basically to supply something with a callback, and that’s it!
Composing a Program from Monads
Okay, so let’s try to use our monads to make an actual program. Say we have a file with a list of URLs and we want to fetch each of these URLs in parallel. Then, we want to cut the responses to 200 bytes each for brevity and print out the result.
We start off by converting existing language APIs to monadic interfaces (see the functions readFile
and fetch
). Now that we have that, we can just compose them to get the final result as one chain. Note that the chain itself is super safe, as all the gory details are contained in monads.
JavaScript—Sample Monad Program
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)
Python—Sample Monad Program
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()
Ruby—Sample Monad Program
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
Swift—Sample Monad Program
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()
Scala—Sample Monad Program
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! Awesome!
Understanding the basics
What is the meaning/definition of a monad?
A monad is an abstract interface that defines “pure” and “flatMap” functions. Pure lets you convert an ordinary value to monadic value. FlatMap allows functions with ordinary arguments to be applied to monadic arguments.
What are monads for?
Monads are used extensively in functional programming. Their key goal is isolating any unreliable and dangerous side effects in one place, so you can enjoy safe programming in all other parts of the app.
What is a monad category?
Technically, a monad is an endofunctor, meaning that it’s something that maps a category to itself. But you can think of an image of that functor as a new category with monadic side effect(s).
What is monad programming?
Monad programming is a technique of composing different monadic values into one big monad. After that it’s easy to process all side effects, because they are concentrated just in one monad, rather than many monads.
Moscow, Russia
Member since June 26, 2017
About the author
Alexey (MEcon) is skilled in several languages and prefers functional programming, particularly Scala, to lower time wasted hunting bugs.