Monads for Developers with a Background in OO
Monads for Developers with a Background in OO #
This article will try to explain what Monads are from an OO perspective.
More specifically how Monads solves a class of problems typically
solved differently in OO. It assumes
that you are reasonably well-versed in Java 8 features such as
Optional and Streams.
Monads as an Abstraction #
As you probably know, FP puts more emphasis than OO on immutable state and
pure functions. In OO we usually solve “secondary concerns” like logging and metrics by
using side-effects. A member function might write to stdout directly, or
use some sort of mockable “Logger” interface, which we can use to inject
mocks to verify correct behaviour:
public static int impureAdd(int i, int j) {
System.out.printf("Adding %s and %s", i, j);
return i + j;
}
In FP, this is not considered good design. Instead, you are encouraged to
have your functions return the data they produce directly. So if you
produce logging, you “should” add the log rows to your return value.
One very straight-forward way to do so is using wrappers. So if your
function normally returns int, it will return Logged<Integer> after you
have added logging. The Logged wrapper then contains the log rows in
addition to the value it wraps:
class Logged<T> {
public T value;
public final List<String> logStatements;
public Logged(T value, List<String> logStatements) {
this.value = value;
this.logStatements = logStatements;
}
}
public static Logged<Integer> loggedAdd(int i, int j) {
return new Logged<>(i + j, asList(String.format("Adding %s and %s", i, j)));
}
So far soo good. Now let’s consider function chaining, something which is
basically the foundation in FP and therefore important to get right.
Chaining with pure functions is no problem:
// Chaining function calls is no problem with pure functions
int result = add(add(1, 2), 3);
assertEquals(6, result);
But the same unfortunately cannot be said about the wrapped version. You
have to manually unwrap the first wrapper, call the second function
with the unwrapped value and finally concat the lists of logs:
Logged<Integer> r1 = loggedAdd(1, 2);
// First we call the next function with the previous return value
Logged<Integer> r2 = loggedAdd(r1.value, 3);
// Then the total logged result is formed by taking the latest return value
// and the concatenation of the log lines.
Logged<Integer> result = new Logged<>(r2.value, concatLists(r1.logStatements, r2.logStatements));
assertEquals(6, (int) result.value);
assertEquals(asList("Adding 1 and 2", "Adding 3 and 3"), result.logStatements);
Really ugly! The question becomes: can we come up with a (functional) way
of abstracting this chaining? It turns out that you can generalize a
higher-order function which abstracts this combining:
private static <T, P> Logged<P> bind(Logged<T> prev, Function<T, Logged<P>> f) {
// First we call the next function with the previous return value
Logged<P> r1 = f.apply(prev.value);
// Then the total logged result is formed by taking the latest return value
// and the concatenation of the log lines.
return new Logged<>(r1.value, concatLists(prev.logStatements, r1.logStatements));
}
So, given the previous wrapped result, prev, and the next function in the
chain, f, this function calls the next function with the result of the
last addition and combines the logs correctly.
The problem of adding 1, 2 and 3 then becomes:
Logged<Integer> total = bind(loggedAdd(1, 2),
r2v -> loggedAdd(r2v, 3));
assertEquals(6, (int) total.value);
assertEquals(asList("Adding 1 and 2", "Adding 3 and 3"), total.logStatements);
To illustrate that this applies to more than just logged integers,
consider the problem of adding 1 and 2, converting to string and
then appending a suffix to the resulting string, all in a logged
fashion:
private static Logged<String> loggedToString(int i) {
return new Logged<>(String.valueOf(i), asList("Converting " + i + " to string"));
}
private static Logged<String> loggedConcat(String s1, String s2) {
return new Logged<>(s1 + s2, asList("Concatenating " + s1 + " and " + s2));
}
@Test
public void bindDifferentFunctions() throws Exception {
// Now we can write chains of bind
Logged<String> total = bind(loggedAdd(1, 2),
r1v -> bind(loggedToString(r1v),
r2v -> loggedConcat(r2v, "-woho")
)
);
assertEquals("3-woho", total.value);
assertEquals(asList("Adding 1 and 2", "Converting 3 to string", "Concatenating 3 and -woho"), total
.logStatements);
}
As you can see, we hid the knowledge on how Logged wrappers must be
combined inside bind. So for a user, as long as they use bind, they
don’t have to care about how the Logged wrappers have to be combined.
It will happen correctly inside bind. In fact, a user doesn’t ever
need to peek inside the Logged wrapper while chaining function calls.
This allows an implementer to make all data inside
a Logged wrapper private and effectively make the correct
composition of Logged wrappers mandatory. It would then become impossible
for a user to incorrectly interleave log rows or propagate the incorrect
value to the next step in the function chain.
This is sort of a powerful abstraction, since it allows for a wrapper
to fully protect and own its data and to dictate how it is chained.
And this, ladies and gentlemen, is a Monad. A wrapper which implements
bind.
But it’s Unreadable #
Yes, that’s true. But it’s a lot more readable in infix form, so that instead
of writing for instance bind(a, r0v -> loggedAdd(r0v, 1)), you can
write a bind (r0v -> loggedAdd(r0v, 1)). Haskell even calls bind >>=, so
that it looks more as an operator: a >>= (r0v -> loggedAdd(r0v, 1)). They
then go even further and enable you to write it in “do-notation”:
do {
result <- loggedAdd a 1
}
, which is then automatically de-sugared into a chain of binds.
Why Is this Pattern Called a Monad? #
We have just defined Loggable and it’s implementation of bind.
Together the constructor of Loggable and the higher-order function bind
are able to transform types and functions on those types into their wrapped
counterparts.
It turns out that the concept of transforming both types and
functions into a “wrapped domain” is already a thing within category theory.
We are doing it by means of a type constructor and a higher-order function,
but category theory says nothing about how you do it. It only talks about
the general concept on a higher level.
More specifically, a category consists of a collection of
objects and a collection of mappings between them called morphisms.
A functional program can be viewed as a category with types as objects
and functions as morphisms.
Additionally, you can view all types and functions as one category,
and all “wrapped” types and functions as another category. The
category of wrapped types and functions is a subcategory to the general category.
Something transforming both objects and morphisms into another category,
like we do when we move from the general category to the wrapped,
is called a functor in category theory. Since our transform moves
to a subcategory, we technically stay inside the same general category
of types and functions.
A functor which goes back to the source category like this is called
an endofunctor.
A monad is just such an endofunctor with some additional constraints:
- You have to have a way of “constructing a wrapped object from a non-wrapped”. This tranformation is usually called unit or return.
- You have to be able to repeatedly apply the transform. In other words,
chain operations. Since this typically
results in double-wrapping, you need an “un-doublewrap” function, typically
called
join.
It can be shown that join is equivalent to binding to the identity function.
So generally speaking, a Monad is just the generalized concept of this “wrapped domain”.
How Does this Relate to Optional? #
Well, bind as we defined it above is usually called flatMap in Java
and Scala. Consider this example dividing Optional<Integer>:
Optional<Integer> divide(int i, int j) {
if (j == 0) {
return Optional.empty();
}
return Optional.of(i / j);
}
@Test
public void flatMapOptional() throws Exception {
Optional<Integer> r1 = Optional.of(3).flatMap(i -> divide(i, 3));
assertEquals(r1, Optional.of(1));
Optional<Integer> r2 = Optional.of(3).flatMap(i -> divide(i, 0));
assertEquals(r2, Optional.empty());
}
Here we can see that instead of calling
bind(Optional.of(3), i -> divide(i, 3)), we made bind a member function:
Optional.of(3).bind(i -> divide(i, 3)), and then renamed bind to
flatMap.
Why the flatMap name? Well, because you produce a new wrapped value from
the previous wrapped value, and then flatten the result into a single wrapping layer.
Just the kind of un-doublewrapping which what we talked about for the join operator.
So flatMap, join and bind are three names for the same concept of
“controlled un-doublewrapping while protecting wrapper data
and preserving the wrapper invariants”.
What About Streams? #
Java Streams work for many different types and has fancy features.
But if we focus on transforming lists, Streams are just a fancy way of defining
bind for lists. We can do just that:
private static <T, P> List<P> bind(List<T> r0, Function<T, List<P>> f) {
ArrayList<P> result = new ArrayList<>();
for (T t : r0) {
result.addAll(f.apply(t));
}
return result;
}
With this definition we can map simple elements:
@Test
public void bindForListMap() throws Exception {
List<Integer> is = bind(asList(1, 2, 3), i -> asList(-i));
assertEquals(asList(-1, -2, -3), is);
}
And we can also do bind chains:
@Test
public void bindForListFlatMap() throws Exception {
List<Integer> is = bind(asList(1, 2, 3),
i -> bind(asList(-i, i),
i2 -> asList(i2 * 2)));
assertEquals(asList(-2, 2, -4, 4, -6, 6), is);
}
The Programmable Semicolon #
Bind chains gives significant power to the bind function. It can
for instance short-circuit evaluation. This can be seen when
using Optional in chains where each step may fail. Consider
a way of getting a user:
Optional<User> getUser() {...}
And some code to extract the name of the boss of that user:
Optional<String> employerDeparmentHeadName = getUser()
.map(u -> u.getEmployer())
.map(e -> e.getDepartment())
.map(d -> d.getHead())
.map(h -> h.getName());
Such a pipeline can fail in any stage and will still not cause
a runtime error.
We can implement our own Optional type to show how
this is done. But let’s call it Maybe instead to not cause
confusion:
static class Maybe<T> {
private final T value;
private Maybe(T value) { this.value = value; }
public static <T> Maybe<T> just(T value) { return new Maybe<>(value); }
public static <T> Maybe<T> none() { return new Maybe<>(null); }
public boolean isNone() { return value == null; }
public T get() {
if (isNone()) {
throw new IllegalStateException("Is none");
}
return value;
}
}
private static <T, P> Maybe<P> bind(Maybe<T> r0, Function<T, Maybe<P>> f) {
if (r0.isNone()) {
return Maybe.none();
}
return f.apply(r0.value);
}
The bind function short-circuits evaluation
as soon as the pipeline encounters a none value. Let’s see an
example of a division pipeline, which will fail a soon as you try
to divide by 0:
private static Maybe<Integer> maybeDivide(int i, int j) {
if (j == 0) {
return Maybe.none();
}
return Maybe.just(i / j);
}
@Test
public void chainMaybe() throws Exception {
// Now we can write a chain of operations on a Maybe<int>
Maybe<Integer> total = bind(maybeDivide(10, 2),
r1v -> maybeDivide(r1v, 2)
);
assertEquals(2, (int) total.get());
// But as soon as we divide by 0, we end up with a 'None' maybe,
// and the chain aborts according to the rules of bind.
Maybe<Integer> total2 = bind(maybeDivide(10, 0),
r1v -> maybeDivide(r1v, 2)
);
assertTrue(total2.isNone());
}
This power over how statements are chained has led to Monads being
called “programmable semicolons”. This is of course only true for
bind chains, but still it demonstrates that Monads are
powerful abstractions, since they give you the ability to
affect how statements are chained.
Summary #
When writing functional programs you cannot rely on side effects. So
“secondary data” has to be returned from functions. A handy way of
doing so is by using wrappers. When chaining function calls, you need
to both control how secondary data is combined as well as how primary
data is fed from the result of the previous function as an argument
to the next.
You want this combination logic centralized and specific per wrapper
type. It turns out that a good approach is to not expose the data
of the wrapper, but rather to send the next function to the wrapper
and let it maintain its own invariants.
The function which implements this logic is commonly known as
bind or flatMap.
This approach can be seen as a way of wrapping both types and functions
into their wrapped counterpart. The monad can alter the functionality
of both values and functions on those values. This type of construct
is called a monad in category theory.