Functors and Monads in Java - Don't fear Algebra.

Functors


Before we explain what a monad is, let's explore simpler construct called a functor . A functor is a typed data structure that encapsulates some value(s). From a syntactic perspective a functor is a container with the following API:
import java.util.function.Function;
interface Functor<T> {
    <R> Functor<R> map(Function<T, R> f);
}

But mere syntax is not enough to understand what a functor is. The only operation that functor provides is map() that takes a function f. This function receives whatever is inside a box, transforms it and wraps the result as-is into a second functor. Please read that carefully. Functor<T> is always an immutable container, thus map never mutates the original object it was executed on. Instead, it returns the result (or results - be patient) wrapped in a brand new functor, possibly of different type R. Additionally functors should not perform any actions when identity function is applied, that is map(x -> x). Such a pattern should always return either the same functor or an equal instance.
Often Functor<T> is compared to a box holding instance of T where the only way of interacting with this value is by transforming it. However, there is no idiomatic way of unwrapping or escaping from the functor. The value(s) always stay within the context of a functor. Why are functors useful? They generalize multiple common idioms like collections, promises, optionals, etc. with a single, uniform API that works across all of them. Let me introduce a couple of functors to make you more fluent with this API:
interface Functor<T,F extends Functor<?,?>> {
    <R> F map(Function<T,R> f);
}
class Identity<T> implements Functor<T,Identity<?>> {
    private final T value;
    Identity(T value) { this.value = value; }
    public <R> Identity<R> map(Function<T,R> f) {
        final R result = f.apply(value);
        return new Identity<>(result);
    }
}

An extra F type parameter was required to make Identity compile. What you saw in the preceding example was the simplest functor just holding a value. All you can do with that value is transforming it inside map method, but there is no way to extract it. This is considered beyond the scope of a pure functor. The only way to interact with functor is by applying sequences of type-safe transformations:
Identity<String> idString = new Identity<>("abc");
Identity<Integer> idInt = idString.map(String::length);

Or fluently, just like you compose functions:
Identity<byte[]> idBytes = new Identity<>(customer)
        .map(Customer::getAddress)
        .map(Address::street)
        .map((String s) -> s.substring(0, 3))
        .map(String::toLowerCase)
        .map(String::getBytes);

From this perspective mapping over a functor is not much different than just invoking chained functions:
byte[] bytes = customer
        .getAddress()
        .street()
        .substring(0, 3)
        .toLowerCase()
        .getBytes();

Why would you even bother with such verbose wrapping that not only does not provide any added value, but also is not capable of extracting the contents back? Well, it turns out you can model several other concepts using this raw functor abstraction. For example starting from Java 8 Optional is a functor with the map() method. Let us implement it from scratch:
class FOptional<T> implements Functor<T,FOptional<?>> {
    private final T valueOrNull;
    private FOptional(T valueOrNull) {
        this.valueOrNull = valueOrNull;
    }
    public <R> FOptional<R> map(Function<T,R> f) {
        if (valueOrNull == null)
            return empty();
        else
            return of(f.apply(valueOrNull));
    }
    public static <T> FOptional<T> of(T a) {
        return new FOptional<T>(a);
    }
    public static <T> FOptional<T> empty() {
        return new FOptional<T>(null);
    }
}

Now it becomes interesting. An FOptional<T> functor may hold a value, but just as well it might be empty. It's a type-safe way of encoding null. There are two ways of constructing FOptional - by supplying a value or creating an empty() instance. In both cases, just like with Identity,FOptional is immutable and we can only interact with the value from inside. What differsFOptional is that the transformation function f may not be applied to any value if it is empty. This means functor may not necessarily encapsulate exactly one value of type T. It can just as well wrap an arbitrary number of values, just like List... functor:
import com.google.common.collect.ImmutableList;
class FList<T> implements Functor<T, FList<?>> {
    private final ImmutableList<T> list;
    FList(Iterable<T> value) {
        this.list = ImmutableList.copyOf(value);
    }
    @Override
    public <R> FList<?> map(Function<T, R> f) {
        ArrayList<R> result = new ArrayList<R>(list.size());
        for (T t : list) {
            result.add(f.apply(t));
        }
        return new FList<>(result);
    }
}

The API remains the same: you take a functor in a transformation - but the behavior is much different. Now we apply a transformation on each and every item in the FList, declaratively transforming the whole list. So if you have a list of customers and you want a list of their streets, it's as simple as:
import static java.util.Arrays.asList;
FList<Customer> customers = new FList<>(asList(cust1, cust2));
FList<String> streets = customers
        .map(Customer::getAddress)
        .map(Address::street);

It's no longer as simple as saying customers.getAddress().street(), you can't invokegetAddress() on a collection of customers, you must invoke getAddress() on each individual customer and then place it back in a collection. By the way, Groovy found this pattern so common that it actually has a syntax sugar for that: customer*.getAddress()*.street(). This operator, known as spread-dot, is actually a map in disguise. Maybe you are wondering why I iterate over list manually inside map rather than using Streams from Java 8:list.stream().map(f).collect(toList())? Does this ring a bell? What if I told youjava.util.stream.Stream<T> in Java is a functor as well? And by the way, also a monad?

Now you should see the first benefits of functors - they abstract away the internal representation and provide consistent, easy to use API over various data structures. As the last example let me introduce the promise functor, similar to Future. Promise "promises" that a value will become available one day. It is not yet there, maybe because some background computation was spawned or we are waiting for an external event. But it will appear sometime in the future. The mechanics of completing aPromise<T>are not interesting, but the functor nature is:
Promise<Customer> customer = //...
Promise<byte[]> bytes = customer
        .map(Customer::getAddress)
        .map(Address::street)
        .map((String s) -> s.substring(0, 3))
        .map(String::toLowerCase)
        .map(String::getBytes);

Looks familiar? That is the point! The implementation of the functor is beyond the scope of this article and not even important. Enough to say that we are very close to implementing CompletableFuture from Java 8 and we almost discovered Observable from RxJava. But back to functors. Promise<Customer> does not hold a value of Customer just yet. It promises to have such value in the future. But we can still map over such functor, just like we did with FOptional and FList - the syntax and semantics are exactly the same. The behavior follows what the functor represents. Invoking customer.map(Customer::getAddress) yields Promise<Address>, which means map is non-blocking. customer.map() will customer promise to complete. Instead, it returns another promise, of a different type. When upstream promise completes, downstream promise applies a function passed to map() and passes the result downstream. Suddenly our functor allows us to pipeline asynchronous computations in a non-blocking manner. But you do not have to understand or learn that - because Promise is a functor, it must follow syntax and laws.
There are many other great examples of functors, for example representing value or error in a compositional manner. But it is high time to look at monads.

From Functors to Monads

I assume you understand how functors work and why are they a useful abstraction. But functors are not that universal as one might expect. What happens if your transformation function (the one passed as an argument to map()) returns functor instance rather than simple value? Well, a functor is just a value as well, so nothing bad happens. Whatever was returned is placed back in a functor so all behaves consistently. However imagine you have this handy method for parsing Strings:
FOptional<Integer> tryParse(String s) {
    try {
        final int i = Integer.parseInt(s);
        return FOptional.of(i);
    } catch (NumberFormatException e) {
        return FOptional.empty();
    }
}

Exceptions are side-effects that undermine type system and functional purity. In pure functional languages, there is no place for exceptions. After all, we never heard about throwing exceptions during math classes, right? Errors and illegal conditions are represented explicitly using values and wrappers. For example tryParse() takes a String but does not simply return an int or silently throw an exception at runtime. We explicitly tell, through the type system, that tryParse() can fail, there is nothing exceptional or erroneous in having a malformed string. This semi-failure is represented by an optional result. Interestingly Java has checked exceptions, the ones that must be declared and handled, so in some sense, Java is purer in that regard, it does not hide side-effects. But for better or worse checked exceptions are often discouraged in Java, so let's get back to tryParse(). It seems useful to compose tryParse with String already wrapped in FOptional:
FOptional<String> str = FOptional.of("42");
FOptional<FOptional<Integer>> num = str.map(this::tryParse);

That should not come as a surprise. If tryParse() would return an int you would getFOptional<Integer> num, but because map() function returns FOptional<Integer> itself, it gets wrapped twice into awkward FOptional<FOptional<Integer>>. Please look carefully at the types, you must understand why we got this double wrapper here. Apart from looking horrible, having a functor in functor ruins composition and fluent chaining:
FOptional<Integer> num1 = //...
FOptional<FOptional<Integer>> num2 = //...
FOptional<Date> date1 = num1.map(t -> new Date(t));
//doesn't compile!
FOptional<Date> date2 = num2.map(t -> new Date(t));

Here we try to map over the contents of FOptional by turning int into +Date+. Having a function of int -> Date we can easily transform from Functor<Integer> to Functor<Date>, we know how it works. But in case of num2 the situation becomes complicated. What num2.map()receives as input is no longer an int but an FOoption<Integer> and obviouslyjava.util.Date does not have such a constructor. We broke our functor by double wrapping it. However having a function that returns a functor rather than simple value is so common (liketryParse()) that we can not simply ignore such requirement. One approach is to introduce a special parameterless join() method that "flattens" nested functors:
FOptional<Integer> num3 = num2.join()

It works but because this pattern is so common, special method named flatMap() was introduced. flatMap() is very similar to map but expects the function received as an argument to return a functor - or monad to be precise:
interface Monad<T,M extends Monad<?,?>> extends Functor<T,M> {
    M flatMap(Function<T,M> f);
}

We simply concluded that flatMap is just a syntactic sugar to allow better composition. ButflatMapmethod (often called bind or >>= from Haskell) makes all the difference since it allows complex transformations to be composed in a pure, functional style. If FOptional was an instance of monad, parsing suddenly works as expected:
FOptional<String> num = FOptional.of("42");
FOptional<Integer> answer = num.flatMap(this::tryParse);

Monads do not need to implement map, it can be implemented on top of flatMap() easily. As a matter of fact flatMap is the essential operator that enables a whole new universe of transformations. Obviously just like with functors, syntactic compliance is not enough to call some class a monad, the flatMap() operator has to follow monad laws, but they are fairly intuitive like associativity of flatMap()and identity. The latter requires that m(x).flatMap(f) is the same asf(x) for any monad holding a value x and any function f. We are not going to dive too deep into monad theory, instead let's focus on practical implications. Monads shine when their internal structure is not trivial, for example Promisemonad that will hold a value in the future. Can you guess from the type system how Promise will behave in the following program? First, all methods that can potentially take some time to complete return a Promise:
import java.time.DayOfWeek;
Promise<Customer> loadCustomer(int id) {
    //...
}
Promise<Basket> readBasket(Customer customer) {
    //...
}
Promise<BigDecimal> calculateDiscount(Basket basket, DayOfWeek dow) {
    //...
}

We can now compose these functions as if they were all blocking using monadic operators:
Promise<BigDecimal> discount = 
    loadCustomer(42)
        .flatMap(this::readBasket)
        .flatMap(b -> calculateDiscount(b, DayOfWeek.FRIDAY));

This becomes interesting. flatMap() must preserve monadic type therefore all intermediate objects are Promises. It is not just about keeping the types in order - preceding program is suddenly fully asynchronous! loadCustomer() returns a Promise so it does not block. readBasket() takes whatever the Promise has (will have) and applies a function returning another Promise and so on and so forth. Basically, we built an asynchronous pipeline of computation where the completion of one step in the background automatically triggers next step.


Reference:

Comments

Post a Comment

Popular Posts