Monads
I decided to write this monad tutorial because I never found a tutorial that worked well for me. Writing this helped to strengthen my own understanding of monads. I welcome feedback and comments, and I’ll correct problems as they’re pointed out to me. Thanks for reading!
I assume you’re comfortable with JavaScript and higher-order functions.
Introduction
Monads define operators to sequence two computations, A and B. Operators behave according to the purpose of their monad. Operators can determine their behavior by the results of A and B, they might not compute A or B, they can loop forever, and they are composed to sequence more than two computations.
The sequence operator is a function that sequences A and B. Its first argument is A and its second argument is B. For example:
function exampleSequence(a, b) {
...
}
The bind operator is a function that sequences A and B and binds a variable in B to A’s result. Its first argument is A and its second argument is a function F:
function exampleBind(a, f) {
...
}
F’s parameter names A’s result and its body is B:
exampleBind(a, function(a) { b })
B can now refer to A’s result by the variable a. Bind applies F to A’s result, thereby binding A’s result to the variable a within B:
function exampleBind(a, f) {
return f(...a...);
}
The return operator is a function that converts values into appropriate arguments for sequence and bind. Its single parameter is the value to convert:
function exampleReturn(x) {
...
}
Maybe Monad
The JavaScript value ages is a list of name and age pairs:
var ages = [["Nick", 24], ["Heidi", 20], ["Miranda", 16]];
getAge returns the age associated with a name:
function getAge(name, ages) {
for (var i = 0; i < ages.length; ++i) {
if (ages[i][0] == name) {
return ages[i][1];
}
}
throw "not found";
}
Adding together Nick and Heidi’s ages:
try {
var nickAge = getAge("Nick", ages);
var heidiAge = getAge("Heidi", ages);
var ageSum = nickAge + heidiAge;
alert(ageSum);
} catch (e) {
alert("error");
}
If both Nick and Heidi are in the list, the addition succeeds; otherwise, it fails. This exception functionality can be implemented using the Maybe monad. The problem of adding ages that might not exist can be generalized to a problem that has zero or one solutions. If a subproblem has zero solutions, the overall problem has zero solutions. We’ll represent zero solutions with Nothing values and one solutions with Just values that contain the solutions:
function Nothing() {
}
function isNothing(x) {
return x instanceof Nothing;
}
function Just(contents) {
this.contents = contents;
}
function isJust(x) {
return x instanceof Just;
}
function fromJust(x) {
return x.contents;
}
getAge redefined to return a Nothing or a Just:
function maybeGetAge(name, ages) {
for (var i = 0; i < ages.length; ++i) {
if (ages[i][0] == name) {
return new Just(ages[i][1]);
}
}
return new Nothing();
}
Adding together Nick and Heidi’s ages:
var nickAge = maybeGetAge("Nick", ages);
if (isNothing(nickAge)) {
alert("error");
}
var heidiAge = maybeGetAge("Heidi", ages);
if (isNothing(heidiAge)) {
alert("error");
}
var ageSum = fromJust(nickAge) + fromJust(heidiAge);
alert(ageSum);
If Nick’s name does not exist (Nothing), the addition aborts (Nothing) because it requires his age. If Nick’s name exists (Just), but Heidi’s name does not (Nothing), the addition aborts (Nothing) for the same reason. In other words, for a sequence of ages, if any age is Nothing, the sequence is Nothing. This is the Maybe monad — maybe there’s a solution, maybe there’s not.
maybeSequence sequences Nothing and Just values:
function maybeSequence(a, b) {
if (isNothing(a)) {
return a;
} else {
return b;
}
}
maybeSequence can be composed one or more times to sequence more than two Maybe computations:
var mirandaAge = maybeSequence(maybeGetAge("Nick", ages),
maybeSequence(maybeGetAge("Heidi", ages),
maybeGetAge("Miranda", ages)));
mirandaAge is a Just. If any names didn’t exist, mirandaAge would be a Nothing.
We can sequence ages with maybeSequence, but we need maybeBind to add them:
function maybeBind(a, f) {
if (isNothing(a)) {
return a;
} else {
return f(fromJust(a));
}
}
Recall that F is a function that contains B. If A is a Just, maybeBind gets A’s solution and applies F to it. maybeBind can be composed one or more times to sequence more than two Maybe computations:
var ageSum = maybeBind(maybeGetAge("Nick", ages), function (nickAge) {
return maybeBind(maybeGetAge("Heidi", ages), function (heidiAge) {
return new Just(nickAge + heidiAge);
})
});
ageSum is now a Maybe value, a Nothing or a Just, which a single check can handle:
if (isNothing(ageSum)) {
alert("error");
}
A sequence of multiple Maybe computations can thus be reduced to a single value and handled at a single point.
maybeReturn puts a solution into a Just:
function maybeReturn(x) {
return new Just(x);
}
JavaScript’s syntax doesn’t make functional programming easy, so these examples may seem verbose and ugly. However, in a pure functional language like Haskell, an equivalent implementation of the Maybe monad is simple, concise, and beautiful:
data Maybe a = Nothing | Just a
maybeSequence Nothing _ = Nothing
maybeSequence (Just a) b = b
maybeBind Nothing _ = Nothing
maybeBind (Just a) b = b a
maybeReturn = Just
A monad can abstract verbose programming constructs, thereby modularizing code and hiding implementation details. There are diverse applications for monads; the trick is to recognize when a monad can solve your problem.
Type Classes And Monads
Monads in Haskell are difficult to learn because types and type classes obscure the core ideas of monads. This section will explain how monads work with type classes.
Polymorphism And Type Classes
In Haskell, there are two types of polymorphism. Parametric polymorphism parameterizes the types of functions with type variables. Haskell can reconstruct the types of all expressions, even where type annotations are absent, and instantiates types that contain type variables automatically. For example, the declaration const x y = x defines a function with type a -> b -> a. Haskell reconstructs this type for you behind the scenes and silently instantiates the type variables as the function is used. If const is applied to 1 and 2, a and b are first instantiated with Int. Since const, and indeed all parametric polymorphic functions, is meant to work for arguments of any type, it cannot know the actual types of its arguments.
Ad-hoc polymorphism determines function behavior by the types of function arguments, which would seem to be the opposite of parametric polymorphism. Overloading in other languages, where functions with different type signatures are defined with the same name, is an instance of ad-hoc polymorphism. Haskell provides ad-hoc polymorphism in the form of type classes. A type class declares a set of functions and their types in the context of a single type parameter.
class Eq a where
(==), (/=) :: a -> a -> Bool
Above, the type class Eq, parameterized by the type variable a, declares two functions, (==) and (/=) with type a -> a -> Bool.
The type class can then be instantiated with a type, where the type class’s declarations are defined.
instance Eq Int where
x == y = x `intEquals` y
x /= y = not (x == y)
The type class’s parameter is instantiated with Int, and the types of (==) and (/=) become Int -> Int -> Bool within the context of their definitions for this type class instantiation. Now, whenever (==) or (/=) are applied to Int arguments, these specific definitions of them will be used. More Eq instances can be declared, and the types of the arguments for (==) and (/=) determine which instance definitions to use.
Parametric polymorphism, in the form of type variables, parameterizes the types of functions such that they work arguments of any type, but those functions cannot perform type-specific operations on them. Ad-hoc polymorphism, in the form of type classes, enables functions to take arguments of various types and behave differently depending on their types.
Types And Kinds
The Haskell standard library defines a type class for monads called Monad that declares the sequence, bind, and return functions, as well as a fail function. Understanding types and kinds will help you to better understand how to instantiate the Monad type class for your own monads.
In Haskell, a type can be one of three things:
- a type variable, denoted as a lowercase word, like a, b, or foo;
- a type constructor, denoted as a lowercase word with an uppercase first letter, like A, Eq, or Int;
- or a type application, denoted as two types separated by a space, like a b, Eq a, or Eq Int.
Type applications come into play where types are parameterized with one or more type variables.
data Maybe a = Nothing | Just a
Parameterized types, like Maybe above, are applied to type arguments to instantiate their type parameters. Haskell can automatically infer which type arguments to use, or you can specify yourself with type annotations.
answer :: Maybe Int
answer = Just 1
Every type has a kind. Kinds are used to determine whether types are well-formed. An ill-formed type might apply a type constructor to too few or too many type arguments. Maybe and Maybe Int Char are ill-formed types because the Maybe type has one type parameter.
In Haskell, a kind can be one of two things:
- *, which denotes a type that cannot be applied to another type
- * -> *, which denotes a type that can be applied to another type
Arrow kinds associate to the right, so * -> * -> * is shorthand for * -> (* -> *). Arrow kinds become their right kinds after their types are applied. Maybe has kind * -> *. Applying Maybe to Int gives kind *.
data Foo a b = ...
Foo has kind * -> * -> *. Foo Int has kind * -> *. Foo Int Char has kind *.
Haskell uses three special type constructors:
- function constructors, denoted (->) with kind * -> * -> *;
- list constructors, denoted [] with kind * -> *;
- tuple constructors, denoted (,) with kind * -> * -> *, (,,) with kind * -> * -> * -> *, etc.
Therefore types such as a -> b, [a], and (a, b) are really shorthand for the type applications (->) a b, [] a, and (,) a b, respectively, all with kind *. The latter types are valid Haskell syntax for types.
Monad Type Class
The Monad type class declares the sequence operator as (>>), the bind operator as (>>=), and the return operator as return. I’ll omit the fail operator.
class Monad m where
(>>) :: m a -> m b -> m b
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
The last challenge is to see how these type declarations fit into the understanding of monads that you hopefully now have.
First note that the type class’s type parameter is m, and that m is applied to a type in every type declaration. This means that the kind of m is * -> *.
instance Monad X where ...
This means X, from above, whatever X may be, must also have kind * -> *. Maybe and [] come to mind.
data Maybe a = Nothing | Just a
instance Monad Maybe where
Nothing >> _ = Nothing
(Just a) >> b = b
Nothing >>= _ = Nothing
(Just a) >>= b = b a
return = Just
Let’s examine how these definitions correspond to the types declared by the Monad type class. (>>) has type m a -> m b -> m b. In our case, m is Maybe, so the type is really Maybe a -> Maybe b -> Maybe b. This is a function that takes two arguments and returns something. Judging by the result type, the function returns its second argument, because the second argument and the result share the b type variable. This matches our earlier understanding of sequence: the first argument is computed, then the second, and the overall result is the second.
(>>=) has type m a -> (a -> m b) -> m b. The only difference is its second function argument. Note that the type argument a in the first function argument type m a also occurs as the function argument type in the second function argument type a -> m b. Let’s say a and b are Int such that the type is now Maybe Int -> (Int -> Maybe Int) -> Maybe Int.
