Posts Tagged ‘java’
flatMap on the Monad in Java
Imagine writing entire programs by coding only what is necessary.
Now create an abstraction for that.
There was a time when OO was considered king. Those days are over. FP is leaking into every modern JVM language and the functional programming community is pushing boundaries. This has introduced new challenges for traditional Java programmers. We need to learn some FP.
One way to ease our way into learning FP is to learn some Scala. The expressive power of functional programming quickly becomes apparent when you learn to use map, flatMap, filter, and friends. But then, just as you begin to feel comfortable with these, someone comes along and utters the phrase “flatMap on the monad”. flatMap on the what? They try to explain, but it goes over your head. You think nothing of it and move on with learning more FP. But before too long, you stumble upon a random blog somewhere where someone is raving about “the Maybe monad”. There’s that ‘M’ word again! It seems that the entire FP community knows what a monad is, but you do not. You try to read along and follow, but struggle. You tell yourself to think harder and read again. You struggle again. At this point you can choose to either keep going round in circles or put aside everything you think you know about FP and start learning it.
After about two years of going back to basics and studying up on some programming history, lambda calculus, logic, a little bit of math, and experimenting with OO and FP, I believe I have finally got it! It has perhaps taken me a lot longer than it should have, but I wouldn’t change a minute of it. If you’re interested in seeing monads in Java, this might be for you!
Functions
In FP there are no variables and objects, only constants and functions. Functions are first class citizens. You can pass them as arguments, return them as values, and assign names to them. You can apply functions anywhere where values are expected. Functions map input values to output values. The general form of a function is:
T -> U
Here we are using the standard Java naming conventions for types. This is a function that accepts a parameter of type T and returns a result of type U, commonly referred to as: “a T to U function”. Pure functions produce output based on input and do nothing else. They always produce the same output for a given input, do not modify any state, and produce no side effects. They are known to be what is termed ‘referentially transparent’, which means that for a given input, you can replace a function with its output throughout a program without impacting behavior. Achieving referential transparency with Java will require some discipline on our behalf, since most data structures are mutable.
Functions only execute and produce output when they are applied to an input. They do nothing otherwise. You can think of them as reusable pieces of result yielding code. We need functions to implement monads for three reasons:
- To accept functions as input
- To return functions as output
- To defer execution
There are no functions in Java, so the first thing we need to do is define our own function type. We will define this as a single method interface as follows:
Function
public interface Function<T, U> {
U apply(T arg);
}
With this interface in place, we can define objects that emulate functions and apply them to values (or other functions). We can define functions either through anonymous inner instances of this interface or through named classes that implement it. As with any other Java interface, we can pass Function references as arguments, return them as results, and store them in variables. For example, we could define a utility function for creating and returning bean property getter functions like this:
@SuppressWarnings("unchecked")
public static <T, U> Function<T, U> getter(final String property) {
return new Function<T, U>() {
public U apply(T bean) {
try {
Method getter =
new PropertyDescriptor(property, bean.getClass()).getReadMethod();
return (U) getter.invoke(bean);
} catch (Exception e) {
return null;
}
}
};
}
/* Sample Usage */
// Create a ContactInfo.email property getter function
Function<ContactInfo, String> getEmail = getter("email");
// Apply the getter function to a contactInfo bean to get email address
String email = getEmail.apply(contactInfo);
You may have noticed that the apply method in the Function interface does not declare to throw any exceptions. This was done deliberately in the interest of preserving referential transparency. That’s right, throwing an exception is considered a side effect. Unfortunately there is no escaping checked exceptions in Java, so you will need to handle any checked exceptions that may occur in your functions (tip: do not throw checked exceptions). Runtime exceptions on the other hand are legitimate errors that we will treat as failures (tip: do not use this as an excuse to wrap and throw checked exceptions in runtime exceptions).
Functors
Now that we have a way to define functions, we can move on to the next thing we need to define monads; functors. A functor is a generic type that gives meaning or context to a value of some type. You can think of a functor as a kind of typed object. All monads are functors. To apply a function to a value in a functor, we need to somehow get the function into the functor where it can be applied. We can do this through a function called fmap which looks like this (where F is for Functor):
(T -> U) -> (F[T] -> F[U])
This is a function that maps a T -> U function to a F[T] -> F[U] function. (We use square brackets instead of angle brackets to denote parameterized types to avoid confusion with the functional arrow syntax). You can think of fmap as either a function that maps over a function, or as a function that lifts a function. Either way, it provides a means of applying a function to a value in a functor through a wrapper function. We will define Functor as an abstract class instead of an interface so that we can restrict public access to fmap (later on we will implement a public method at the monad level called map which will implicitly apply fmap to the current instance).
Functor
public abstract class Functor<F, T> {
protected abstract <U> Function<? extends Functor<F, T>, ? extends Functor<?, U>>
fmap(Function<T, U> f);
}
Type F is the parameterized type of the functor. A concrete implementor can pass itself or a generic type that it implements in as this type. Types T and U are the input and output types of the function argument f in fmap. T is provided as a parameter and U is inferred by the compiler.
Let’s go through an example to get a feel for how fmap works. Imagine that you have a functor that is a box with a value in it that is not accessible from the outside. The box has no getters or setters, only the fmap function. How do you apply a function to the value in the box and get another box with the result of the function in it? The solution is to create a function that can be applied to the value and then apply fmap to that to get another function that when applied will return the new box.
public class Box<T> extends Functor<Box<T>, T> {
private T value;
public Box(T value) {
this.value = value;
}
@Override
public <U> Function<Box<T>, Box<U>> fmap(final Function<T, U> f) {
return new Function<Box<T>, Box<U>>() {
public Box<U> apply(Box<T> box) {
return new Box<U>(f.apply(box.value));
}
};
}
}
// create an increment function
Function<Integer, Integer> increment = new Function<Integer, Integer>() {
public Integer apply(Integer num) {
return num + 1;
}
};
// create a box with 1 in it
Box<Integer> box1 = new Box<Integer>(1);
// create a box that has the incremented value of box1 in it
Box<Integer> box2 = box1.fmap(increment).apply(box1);
So now that we have functions and functors, let’s move on to monads.
Monads
What is a monad?
A monad is a typed object that can be mapped to other typed objects in a functional way. It is a functor capable of performing one or many operations in a single computation. This capability is facilitated through a bind function which maps a value in one functor to another functor through a given function. This allows processing pipelines to be constructed, where the output of one function is piped through as input to a next function in a chain of functions. The bind function looks like this (where M is for Monad):
M[T] -> (T -> M[U]) -> M[U]
This function accepts a value of type M[T] and returns a value of type M[U] through a given function T -> M[U]. Following this through from left to right, you could be forgiven for thinking that we could do this by directly applying T -> M[U] to the T in M[T] and returning the result M[U]. But before we can even apply this function to T, we need to first put it into the same context as T. T is in M. Therefore we need to put the function into M. We cannot simply apply it to T from the outside, since from the outside we have M[T] and we cannot apply a function that accepts a T to a value of type M[T]. Recall that a monad is a functor, and to apply a function to a value in a functor we need to go through fmap (kind of like we did in our box functor example above). So bind will still look like the above to a caller, but its implementation will look like this:
M[T] -> (T -> M[U]) -> (M[T] -> M[M[U]]) -> M[U]
We’ll now compose this by using fmap to lift the given T -> M[U] function up one level:
fmap(T -> M[U]) = M[T] -> M[M[U]]
Substituting this into the above, we get:
M[T] -> fmap(T -> M[U]) -> M[U]
Let mt = an instance of type M[T]
Applying the above to mt, we get:
fmap(T -> M[U])(mt) -> M[U]
Let f = the function T -> M[U]
Substituting f, gives us:
fmap(f)(mt) -> M[U]
We now introduce a function called join to flatten the lifted output of fmap(f)(mt) back down one level.
join(M[M[U]]) = M[U]
We combine the two functions to get:
bind(f) = join(fmap(f) (mt))
In our Java implementation, bind, join, and fmap, will be methods on object mt. For convenience, and to eliminate the redundancy of calling fmap on mt and applying the returned function to mt, we’ll introduce a new map function to do it implicitly so that:
mt.map(f) = mt.fmap(f)(mt)
Replacing fmap with map, we get:
bind(f) = join(map(f))
We have composed bind in terms of map and join, and map in terms of fmap. If we were to rename join to flat (since join makes things flat), we would have:
bind(f) = flat(map(f))
Remind you of anything? Hey yeah, it’s flatMap! So that’s what that “flatMap on the monad” thing is all about!
To simplify our Java implementation we will make the join function a parameterless method that can be called directly on a lifted M[M[U]] result.
bind(f) = map(f).join()
Now let’s have a look at how we will implement fmap. We know that fmap will accept a T -> M[U] function and return a M[T] -> M[M[U]] function. This returned function when applied to M[T] will return a result of type M[M[U]]. It will do this by lifting the result of the original T -> M[U] function one level up into M. For this purpose, we will define a function called unit that can lift any value into M. It will look like this:
U -> M[U]
The unit function will lift both values and functions into M. It will lift values of type U to M[U] and values of type M[U] to M[M[U]], and functions of type T -> U to M[T -> U] and functions of type T -> M[U] to M[T -> M[U]], and so on.
Composing fmap in terms of unit:
fmap(T -> M[U]) = M[T] -> M[M[U]] = M[T] -> M[T -> M[U]] = M[T] -> unit(T -> M[U])
Notice that we are using unit here to lift the T -> M[U] function into M to get:
M[T -> M[U]]
Monads are Applicative Functors
The T -> M[U] function is now lifted into M. So both the function and the value that we want to apply it to are in M. But how do we apply a lifted function M[T -> M[U]] to a lifted value M[T]? The solution is introduce a function that will map the lifted function to another function that when applied to M[T], will extract and apply the T -> M[U] function to T inside M and return the result M[U] lifted into M. The introduced function will look like this:
M[T -> M[U]] -> M[T] -> M[M[U]]
The general form of this function is:
M[T -> U] -> M[T] -> M[U]
This is the signature of what is known as an applicative functor. It takes a function in M and applies it to a value in M and returns the result in M. It effectively just applies a function in the context of M. This is exactly what fmap will do for all monads. So we can say that all monads are applicative functors. We’ll now create an Applicative type class to capture this in a function called apply.
Applicative
public abstract class Applicative<F, T> extends Functor<F, T> {
public abstract <U> U get();
protected abstract <U> Applicative<?, U> unit(U value);
protected final <U> Function<Applicative<F, T>, Applicative<?, U>>
apply(final Applicative<Function<T, U>, U> ff) {
return new Function<Applicative<F, T>, Applicative<?, U>>() {
public Applicative<?, U> apply(Applicative<F, T> ft) {
Function<T, U> f = ff.get();
T t = ft.get();
return unit(f.apply(t));
}
};
}
}
Note that apply also calls unit to lift the result of f. So unit is used twice in every function application; once to lift the function and once again to lift its result.
Now fmap becomes:
fmap(T -> M[U]) = M[T] -> unit(T -> M[U]) = M[T] -> apply(unit(T -> M[U]))
Substituting f, we get:
fmap(f) = M[T] -> apply(unit(f))
Substituting apply(unit(f)) for M[M[U]] in our original bind yields the following complete bind signature:
M[T] -> (T -> M[U]) -> (M[T] -> (M[T -> M[U]] -> M[T] -> M[M[U]])) -> M[U]
The overall effect is a bind operation that performs the following:
- Accepts a T -> M[U] function and lifts it into M
- Applies it to T in M and yields a lifted result M[M[U]]
- Extracts and returns the contained M[U] result
Currently, the function returned by fmap unconditionally invokes apply to yield a lifted result. To give individual monads the opportunity to override this, we will move this logic into a new function called yield and have fmap call that instead. Individual monads that wish to skip over functions and yield their own results can do so by overriding this default yield implementation.
yield(f) = apply(unit(f))
We now compose fmap in terms of yield:
fmap(f) = M[T] -> apply(unit(f)) = M[T] -> yield(f)
Notice here that if yield is overridden, then apply will be bypassed. In a bind scenario, join would then no longer be guaranteed to receive a lifted result. For example, an overridden yield could skip over a function and yield the enclosing monad instance as the intended result. In this case, join would be called on a non lifted value of type M[U] that it would not be able to flatten. Therefore, if yield is overridden to return a non lifted result, then join must also be overridden to return that same result (the same instance that join is invoked on). Otherwise join will error.
We said earlier that we would treat runtime exceptions as failures. So we will introduce one last function called fail to give monads the opportunity to deal with failure in their own way. This function will accept a RuntimeException and return a value of type M[U]. The default implementation will simply rethrow the runtime exception. Monads that wish to introduce their own failure values can override this function.
So finally, fmap becomes:
fmap(f) = M[T] -> (
try {
yield(f)
} catch (RuntimeException e) {
fail(e)
}
)
We now have everything we need to define a monad base class with concrete and final implementations of fmap and apply, default implementations of map, bind, yield, join, and fail, and two abstract methods; unit and get.
Monad
@SuppressWarnings("unchecked")
public abstract class Monad<M, T> extends Applicative<M, T> {
protected Monad() { }
protected <U> Monad<?, U> yield(Function<T, U> f) {
Applicative<Function<T, U>, U> ff = (Applicative<Function<T, U>, U>) unit(f);
return (Monad<?, U>) apply(ff).apply(this);
}
protected <U> Monad<?, U> join() { return get(); }
protected <U> Monad<?, U> fail(RuntimeException e) { throw e; }
protected final <U> Function<Monad<M, T>, Monad<?, U>> fmap(final Function<T, U> f) {
return new Function<Monad<M, T>, Monad<?, U>>() {
public Monad<?, U> apply(final Monad<M, T> mt) {
try {
return mt.yield(f);
} catch(RuntimeException e) {
return mt.fail(e);
}
}
};
}
public <U> Monad<?, U> map(Function<T, U> f) { return fmap(f).apply(this); }
public <U> Monad<?, U> bind(Function<T, ? extends Monad<?, U>> f) {
return map(f).join();
}
}
We can now extend this base class to define specific kinds of monads. Subclasses need only implement unit and get (inherited from Applicative), and override yield, join, and fail where necessary. For stronger type inference, subclasses can override map and bind and change their return types to match the subclass type and delegate to super.map and super.bind respectively.
The Maybe Monad
Now that we have a class for building monads, let’s build one. An easy one to start with is the Maybe monad. A Maybe monad is a container for a value that exists or does not exist. That is; it contains just one value or it contains nothing.
Maybe
@SuppressWarnings("unchecked")
public abstract class Maybe<T> extends Monad<Maybe<T>, T> {
public static <U> Maybe<U> instance(U value) {
return (Maybe<U>) (value != null ? Just.instance(value) : Nothing.instance());
}
@Override public final <U> Maybe<U> map(Function<T, U> f) {
return (Maybe<U>) super.map(f);
}
@Override public final <U> Maybe<U> bind(Function<T, ? extends Monad<?, U>> f) {
return (Maybe<U>) super.bind(f);
}
@Override protected <U> Maybe<U> fail(RuntimeException e) {
return Nothing.instance();
}
public abstract boolean isJust();
public abstract boolean isNothing();
}
Just
@SuppressWarnings("unchecked")
public final class Just<T> extends Maybe<T> {
public static <U> Just<U> instance(U value) { return new Just<U>(value); }
private T value;
private Just(T value) { this.value = value; }
@Override public <U> U get() { return (U) value; }
@Override protected <U> Maybe<U> unit(U value) { return Just.instance(value); }
@Override public boolean isJust() { return true; }
@Override public boolean isNothing() { return false; }
@Override public String toString() { return "Just(" + get() + ")"; }
}
Nothing
@SuppressWarnings({"unchecked", "rawtypes"})
public final class Nothing<T> extends Maybe<T> {
private static final Nothing INSTANCE = new Nothing();
public static <U> Nothing<U> instance() { return INSTANCE; }
private Nothing() { super(); }
@Override public <U> U get() { throw new NoSuchElementException("Nothing.get"); }
@Override protected <U> Maybe<U> unit(U value) { return INSTANCE; }
@Override protected <U> Maybe<U> yield(Function<T, U> f) { return INSTANCE; }
@Override protected <U> Maybe<U> join() { return INSTANCE; }
@Override public boolean isJust() { return false; }
@Override public boolean isNothing() { return true; }
@Override public String toString() { return "Nothing"; }
}
The Maybe base class overrides fail to return Nothing. It has an instance factory method that accepts a value and returns a new instance of Just containing that value if it is not null, or a Nothing otherwise. Both Just and Nothing extend Maybe and implement unit. Nothing additionally overrides yield and join to return itself (which is Nothing). If you map or bind on Just, you will get a new Just with a value. If you map or bind on Nothing, you will get back the same Nothing. How is this useful? It’s best to illustrate with examples.
Consider the following Java code:
String email = bank.getBranch().getContactInfo().getEmail();
Chaining properties like this in Java is dangerous. The bank object could be null and any one of the other getters could return null. They are all NullPointerExceptions waiting to happen. To cater for them, we could do something defensive like this:
String email;
try {
email = bank.getBranch().getContactInfo().getEmail();
} catch (NullPointerException e) {
email = null;
}
return email;
This is neither ideal nor sufficient, as the final result in the email result could still be assigned null. Let’s lift the bank object and all properties into a Maybe monad and use bind. To reduce the redundancy associated with writing anonymous inner Function classes, we’ll write a Maybe getter utility function (one that delegates to the standard getter function we created earlier).
@SuppressWarnings("unchecked")
public static <T, U> Function<T, Maybe<U>> mgetter(final String property) {
return new Function<T, Maybe<U>>() {
public Maybe<U> apply(T bean) {
return (Maybe<U>) Maybe.instance(getter(property).apply(bean));
}
};
}
Function<Bank, Maybe<Branch>> getBranch = mgetter("branch");
Function<Branch, Maybe<ContactInfo>> getContactInfo = mgetter("contactInfo");
Function<ContactInfo, Maybe<String>> getEmail = mgetter("email");
Maybe<String> email =
Maybe.instance(bank).bind(getBranch).bind(getContactInfo).bind(getEmail);
Solved! We now have one Maybe result, and no nulls to worry about. That’s right, they don’t exist anymore. A null property anywhere in the chain will resolve to Nothing and propagate to the result as Nothing without invoking any getters below that point in the chain. This is because our mgetter function lifts every property through the Maybe.instance factory method which returns Nothing if given a null, and a Just otherwise. In the happy scenario, the last bind will return Just(email) as the final result.
The previous example specifically dealt with nulls, but the Maybe monad can be used to deal with any failure. Consider the following:
Function<Integer, BigDecimal> reciprocal = new Function<Integer, BigDecimal>() {
public BigDecimal apply(Integer num) {
return new BigDecimal(1).divide(new BigDecimal(num), 4, RoundingMode.HALF_UP);
}
};
Random random = new Random();
int num = random.nextInt(10);
BigDecimal result = reciprocal.apply(num);
If random returns zero, reciprocal will fail and throw an ArithmeticException (divide by zero error). Unguarded, the exception will propagate and terminate the program. To guard against this and have your program continue, you would have to explicitly catch and handle the exception in some way. For example:
BigDecimal result;
try {
result = reciprocal.apply(num);
} catch (ArithmeticException e) {
result = new java.math.BigDecimal(0); // undefined value = 0 ???
}
Having to handle runtime exceptions like this is really bad, but what makes it terrible is the fact that the failed result of zero is misleading. The reciprocal of zero is definitely not zero! If we instead execute the division inside a Maybe monad, we can do away with the error handling and always get a meaningful result.
Maybe<BigDecimal> result = Maybe.instance(num).map(reciprocal);
Now we’ll get a Just containing the result if num is non zero, or a Nothing otherwise. A guaranteed meaningful result either way. How does this work? Maybe overrides fail to return Nothing, and fmap calls fail whenever a runtime exception occurs.
The Either Monad
Let’s build another monad; the Either monad. Either is a container for a value that can have one of two types. One type is called Left, and the other is called Right. The common convention is to use left for failure values and right for success values, but you can use them to represent any two types of values you like. We will define an Either interface that accepts two type parameters L and R (for left and right respectively). We will extend Monad and implement the Either interface to define a new class called EitherMonad that will be the base for Left and Right. This class will accept three concrete types; L, R, and T. Left will pass in [L, R, L] and Right will pass in [L ,R, R], partially applying L and R respectively through the Monad parameter T. This partial application is necessary since Monad only accepts one concrete type parameter.
Either
public interface Either<L, R> {
Left<L, R> left();
Right<L, R> right();
boolean isLeft();
boolean isRight();
}
Either Monad
@SuppressWarnings("unchecked")
public abstract class EitherMonad<M, L, R, T> extends Monad<M, T>
implements Either<L, R> {
private T value;
protected EitherMonad(T value) { this.value = value; }
public final <U> U get() { return (U) value; }
@Override public final <U> EitherMonad<M, L, R, U> map(Function<T, U> f) {
return (EitherMonad<M, L, R, U>) super.map(f);
}
@Override public final <U> EitherMonad<M, L, R, U>
bind(Function<T, ? extends Monad<?, U>> f) {
return (EitherMonad<M, L, R, U>) super.bind(f);
}
}
Left
@SuppressWarnings("unchecked")
public class Left<L, R> extends EitherMonad<Left<L, R>, L, R, L> {
public static final <L, R> Left<L, R> instance(L value) {
return new Left<L, R>(value);
}
protected Left(L value) { super(value); }
@Override protected <U> Left<U, R> unit(U value) { return instance(value); }
@Override public final Left<L, R> left() { return this; }
@Override public final Right<L, R> right() {
return new Right<L, R>((R) get()) {
@Override protected <U> Right<L, U> yield(Function<R, U> f) {
return (Right<L, U>) this;
}
@Override protected <U> Right<L, U> join() { return (Right<L, U>) this; }
};
}
@Override public final boolean isLeft() { return true; }
@Override public final boolean isRight() { return false; }
@Override public final String toString() { return "Left(" + get() + ")"; }
}
Right
@SuppressWarnings("unchecked")
public class Right<L, R> extends EitherMonad<Right<L, R>, L, R, R> {
public static final <L, R> Right<L, R> instance(R value) {
return new Right<L, R>(value);
}
protected Right(R value) { super(value); }
@Override protected <U> Right<L, U> unit(U value) { return instance(value); }
@Override public final Right<L, R> right() { return this; }
@Override public final Left<L, R> left() {
return new Left<L, R>((L) get()) {
@Override protected <U> Left<U, R> yield(Function<L, U> f) {
return (Left<U, R>) this;
}
@Override protected <U> Left<U, R> join() { return (Left<U, R>) this; }
};
}
@Override public final boolean isLeft() { return false; }
@Override public final boolean isRight() { return true; }
@Override public final String toString() { return "Right(" + get() + ")"; }
}
Both Left and Right implement unit, left and right. Left implements left() by returning the current Left instance and right() to return a new anonymous Right instance containing the current value. The anonymous Right instance overrides yield and join to always return itself. This is to ensure that a map or bind on Left.right() has no effect. On the other hand, a map or bind on Left.left() will return a new Left containing the new result as expected. Conversely, Right is implemented in the same manner.
One use case of Either is to use it as an alternative to throwing exceptions. With this approach, a method that could fail can be defined to return a value of type Either instead of throwing an exception. Callers of that method are then guaranteed a result and can focus all their processing on either success or failure (right or left). A caller that is only interested in success can be completely oblivious to failure. If a failure does occur, it will bypass all operations and transparently propagate to the result and be ignored. If failure does not occur, all operations will execute without having to unnecessarily catch and ignore exceptions that never occur.
Let’s consider an example that involves encoding and uppercasing a string that we know will never fail.
public String encode1(String str) throws UnsupportedEncodingException {
return URLEncoder.encode(str, "utf-8");
}
public Either<UnsupportedEncodingException, String> encode2(String str) {
try {
return Right.instance(URLEncoder.encode(str, "utf-8"));
} catch (UnsupportedEncodingException e) {
return Left.instance(e);
}
}
Function<String, String> toUpper = new Function<String, String>() {
public String apply(String arg) {
return arg.toUpperCase();
}
};
// caller of encode1 has to ignore an exception that will never happen
try {
String encoded = encode1("will always succeed");
encoded = toUpper.apply(encoded);
} catch (UnsupportedEncodingException ignore) {
// will never happen
}
// caller of encode2 can just get on with the job
String encoded = encode2("will always succeed").right().map(toUpper).get();
The List Monad
The Maybe and Either monads that we have created so far deal with only single values. Let’s now create a List monad for dealing with multiple values. Every value in this monad will be a list of zero or many values of some type. When you apply map or bind to a function on a list monad, the function will be applied to every element in the list and the individual results will be returned in a list. For a function that outputs a single value, map will return a list of single value results. For a function that outputs a list, map will return a list of lists where each nested list is a list of results. The bind function of the list monad will only accept functions that return lists. Therefore bind will always return a concatenated (joined) list of all nested results as returned by map. In a list bind, the list is the monad:
List[T] -> (T -> List[U]) -> List[U]
All we have done here is replaced M with List. To implement this, we will define a subclass of Monad called ListMonad that will implement the List interface to delegate to a given list. In this way, the ListMonad will be a list and the outputs of both map and bind will also be lists. We will override yield to operate on all elements of the list, join to concatenate the results, and fail to return an empty list. Additionally, we will add the following useful list functions:
- foldLeft(z, op)where
- z is an initial value of type U
- op is an operator function of type (U -> T) -> U
This function will combine all elements in the list into a single value of type U. It will work from left to right by applying the operator to the original value z and the first element in the list, followed by applying it again to the result of that and the next element in the list, followed by the result of that and the next element, and continue in this manner until the end of the list before returning the accumulated result. yield, join, and reduceLeft will be implemented in terms of this function.
- reduceLeft(op)where
- op is an operator function of type (T -> T) -> T
This function will reduce all elements in the list to a single value of the same list element type T. It will also work from left to right applying the operator to the first and second elements, followed by applying it again to the result of that and the next element, followed by the result of that and the next element, and continue in this manner until the end of the list before returning the accumulated result. It will do this by reusing foldLeft.
- filter(pred)where
- pred is a predicate of type T -> Boolean
This function will return all elements in the list that satisfy a given predicate. This function will be implemented using bind.
There are many other useful list functions we could add, but we will start with only these for our minimal list monad. The foldLeft and reduceLeft functions will accept an operator function requiring two arguments. To support this, we will introduce the following Operator interface:
Operator (2-arg function)
public interface Operator<T, U> {
U apply(U arg1, T arg2);
}
List Monad
@SuppressWarnings("unchecked")
public final class ListMonad<T> extends Monad<List<T>, T> implements List<T> {
public static final <U> ListMonad<U> instance(U value) {
return new ListMonad<U>(Collections.singletonList(value));
}
public static final <U> ListMonad<U> instance(List<U> list) {
return new ListMonad<U>(list);
}
private LinkedList<T> list;
public ListMonad() { this.list = new LinkedList<T>(); }
public ListMonad(List<T> list) { this.list = new LinkedList<T>(list); }
public <U> U get() { return (U) list; }
@Override public final <U> ListMonad<U> map(Function<T, U> f) {
return (ListMonad<U>) super.map(f);
}
@Override public final <U> ListMonad<U> bind(Function<T, ? extends Monad<?, U>> f) {
return (ListMonad<U>) super.bind(f);
}
@Override protected <U> ListMonad<U> unit(U elem) { return instance(elem); }
@Override protected <U> ListMonad<U> fail(RuntimeException e) {
return new ListMonad<U>();
}
@Override protected <U> ListMonad<U> yield(final Function<T, U> f) {
return foldLeft(new ListMonad<U>(), new Operator<T, ListMonad<U>>() {
public ListMonad<U> apply(ListMonad<U> result, T elem) {
result.add(f.apply(elem));
return result;
}
});
}
@Override
protected <U> ListMonad<U> join() {
return foldLeft(new ListMonad<U>(), new Operator<T, ListMonad<U>>() {
public ListMonad<U> apply(ListMonad<U> result, T nested) {
result.addAll((List<U>) nested);
return result;
}
});
}
public <U> U foldLeft(U z, Operator<T, U> op) {
U result = z;
for(T elem : list) {
result = op.apply(result, elem);
}
return result;
}
public T reduceLeft(final Operator<T, T> op) {
if (!list.isEmpty()) {
T head = list.getFirst();
if (list.size() > 1) {
ListMonad<T> tail = instance(list.subList(1, list.size()));
return tail.foldLeft(head, op);
} else { return head; }
} else { throw new UnsupportedOperationException("empty.reduceLeft"); }
}
public ListMonad<T> filter(final Function<T, Boolean> pred) {
return bind(new Function<T, ListMonad<T>>() {
public ListMonad<T> apply(T elem) {
if (pred.apply(elem)) {
return instance(elem);
} else {
return instance(Collections.EMPTY_LIST);
}
}
});
}
@Override public String toString() { return list.toString(); }
// List interface delegator methods..
@Override public boolean add(T e) { return list.add(e); }
// ..remaining delegators omitted for brevity
}
We can do a lot of useful things with the list monad. Here are some examples:
Encrypt a pass phrase:
Function<String, ListMonad<Character>> strToChars =
new Function<String, ListMonad<Character>>() {
public ListMonad<Character> apply(String str) {
ListMonad<Character> chars = new ListMonad<Character>();
for (char ch : str.toCharArray()) {
chars.add(ch);
}
return chars;
}
};
Function<Character, String> encrypt = new Function<Character, String>() {
public String apply(Character ch) {
int intval = ((int) ch) - 32;
int encrypted =
new BigDecimal(intval)
.pow(7).remainder(new BigDecimal(97)).intValue();
return String.format("%02d", encrypted);
}
};
Operator<String, String> concat = new Operator<String, String>() {
public String apply(String str1, String str2) {
return str1 + str2;
}
};
String passPhrase = "The list monad rocks!";
// will return "634920008743820700692742116000142746228201"
String encrypted =
ListMonad.instance(passPhrase).bind(strToChars).map(encrypt).reduceLeft(concat);
Decprypt a pass phrase:
Function<String, ListMonad<String>> encryptedChars =
new Function<String, ListMonad<String>>() {
public ListMonad<String> apply(String str) {
return ListMonad.instance(Arrays.asList(str.split("(?<=\\G.{2})")));
}
};
Function<String, Character> decrypt = new Function<String, Character>() {
public Character apply(String str) {
int decrypted =
new BigDecimal(Integer.parseInt(str))
.pow(55).remainder(new BigDecimal(97)).intValue();
return Character.toChars(decrypted + 32)[0];
}
};
Operator<Character, String> concat = new Operator<Character, String>() {
public String apply(String str, Character ch) {
return str + ch;
}
};
String encrypted = "634920008743820700692742116000142746228201";
// will return "The list monad rocks!"
String passPhrase =
ListMonad.instance(encrypted).bind(encryptedChars).map(decrypt).foldLeft("", concat);
Increment all the numbers in a list:
Function<Integer, Integer> increment = new Function<Integer, Integer>() {
public Integer apply(Integer num) {
return num + 1;
}
}
List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);
// will return [2, 3, 4, 5, 6]
List<Integer> incremented = ListMonad.instance(nums).map(increment);
Sum all the numbers in a list:
Operator<Integer, Integer> plus = new Operator<Integer, Integer>() {
public Integer apply(Integer int1, Integer int2) {
return int1 + int2;
}
};
List<Integer> nums = Arrays.asList(1, 2, 3, 4, 5);
// will return 15
int sum = ListMonad.instance(nums).reduceLeft(plus);
Get the names of all users that have an email address:
public class User {
private String name;
private String email;
public User(String name) { this(name, null); }
public User(String name, String email) {
this.name = name;
this.email = email;
}
public String getName() { return name; }
public String getEmail() { return email; }
}
Function<User, Boolean> hasEmail = new Function<User, Boolean>() {
public Boolean apply(User user) {
return user.getEmail() != null;
}
};
Function<User, String> getName = new Function<User, String>() {
public String apply(User user) {
return user.getName();
}
};
List<User> users = Arrays.asList(
new User("Jack", "jack@acme.com"),
new User("Scott"),
new User("Jill", "jill@acme.com"));
// will return [Jack, Jill]
List<String> names = ListMonad.instance(users).filter(hasEmail).map(getName);
The list monad can also deal with failure. If any element in a list causes a function to fail, then the entire computation will fail and an empty list will be returned.
Function<Integer, Integer> increment = new Function<Integer, Integer>() {
public Integer apply(Integer arg) {
return arg + 1;
}
};
// list with null entry
List<Integer> list2 = Arrays.asList(1, 2, null, 4, 5);
// will return an empty list []
List<Integer> result = ListMonad.instance(list2).map(increment);
There are many other things we can do with monads and many other monads we could go on to create.
Conclusion
Now you may be thinking “What kind of Java programmer writes code like this?”. If you are, then don’t worry. Monads are FP abstractions. They are not well suited for non referentially transparent and imperative code. This and the lack of first class functions in Java makes them a very unnatural fit. Creating a type safe and user friendly interface with generic methods having bounded types is also difficult. The result is less than ideal type inference and code that is scattered with type annotation clutter. But I hope I have demonstrated the usefulness of monads or at least effectively introduced them to Java programmers who may be interested. I would suspect that anyone who is serious about transitioning from OO to FP will at some point find themselves going through a similar learning experience.
Branko Juric
warpedjavaguy 