DRAFT DOCUMENT

Deemed complexity

Functional Programming is sadly still seen by some as a bit of byzantine complexity, or far too theoretical, and certainly not something that will help them in their programming careers.

The above Geek and Poke cartoon is humorous because complexity is never simplified by adding more complexity. In comparison Functional Programming concepts, whilst more complex to learn, are the exact opposite to this cartoon, they’re a different approach to problems and a way to simplify a lot of complexity.

It’s an academic thing

Functional Programming is often simply dismissed as simply an academic thing, but that’s some what to be expected as many articles and blog posts are either too abstract or simply too narrow to demonstrate usefulness. What’s missed however is that even in amongst all this complexity, its concepts have still found their way into almost all of the languages we use every day.

All around us

Concepts like functors and monads are all around us, underpinning many of the popular features we use every day. So when you understand concepts like Functors and Monads; all of suddenly many different language features and abstractions also become more familiar.

The approach behind concepts like Functors and Monads is to encapsulate difference and complexity in order to treat them the same similar concepts.

Monads generalize various seemingly independent concepts so that learning yet another incarnation of monad takes very little time. For example you do not have to learn how CompletableFuture works in Java 8, once you realize it is a monad, you know precisely how it works and what can you expect from its semantics.

And then you hear about Reactive which sounds so much different but because Observable is a monad, there is not much to add. There are numerous other examples of monads you already came across without knowing that.

Value

We all know what a value is! In simple terms it’s an expression that requires no additional processing.

Mutating a value

To mutate the value we need to apply a function which returns

Encapsulated values

A common encapsulation of a value is an array, which can comprise of zero or more encapsulated values.

Mutating encapsulated values

To apply the previous function to these encapsulated values, we need to adjust our approach, because this function expects a single numerical value as input, and not an encapsulation of zero or more values.

The solution to the problem is to iterate over the array’s elements, and pass each value to the function, for example:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Arrays;

public class Example1
{
  static int f(int x)
  {
    return x + 3;
  }

  public static void main(String[] args)
  {
    int[] values = {1, 2, 3, 4, 5};
    for (int i = 0; i < values.length; i++)
    {
      values[i] = f(values[i]);
    }
    System.out.println(Arrays.toString(values)); // [4, 5, 6, 7, 8]
  }
}
OUTPUT : Apply a function to all of encapsulated elements in structure
[4, 5, 6, 7, 8]

It might surprise you that this is the same problem that a functor solves.

Functor

A functor like an array is a typed data structure that encapsulates zero or more; what makes the difference between a standard array and a functor array is the API. Basically a functor provides map, a method that takes a function f, which is then applied to each of the encapsulated values, transforming them and rewrapping these result values into a new functor.

Note:

Following a functional approach the map method does not perform an in-place mutation of the values, but rather creates a new functor with the transformed values, leaving the original functor and its values intact.

Functor laws

All Functional Programming structures adhere to rules; these rules are there to ensure consistency. For an encapsulation structure to be considered a functor it must implement a map method that complies with the following rules:

  • Identity :
  • Composition: must be equivalent to
What is an Identity?

An identity is a function that always returns the same value that was used as its argument.

For example:

Identity test against a collection of values:

[1, 2, 3, 4, 5].map(value => value) must return [1, 2, 3, 4, 5].

What is Composition?

Function composition is the pointwise application of one function to the result of another to produce a third function, whose result is equivalent to the chained application of the first and second functions, for example:

That these two functions and when applied either:

  • all at once
  • or, separately , the result v used as the input to

must end with the same result:

Composition test against a collection of values:

The collection [1, 2, 3, 4, 5] must return the same result [4, 5, 6, 7, 8] for these two implementations:

  • [1, 2, 3, 4, 5].map(v => g(f(v)))
  • [1, 2, 3, 4, 5].map(v => f(v)).map(v => g(v))

Functor implementation

Let’s explore a functor in more detail by looking at a typical syntactical declaration.

Java
1
2
3
4
5
6
import java.util.function.Function;

interface Functor<T> 
{
  <R> Functor<R> map(Function<? super T, ? extends R> f);
}

Mere syntax is usually not sufficient to appreciate what functor is. To recap, a functor provides a map method that takes a function f; this function iterates through whatever is contained within the functor and transforms it and rewraps the result into a new functor, leaving the original intact and unchanged.

Note:

This confirms that by design that the Functor<T> is always and immutable container. The new functor can take on a complete different type during the transformation, for example:

  • Functor<T> => Functor<U>

Quite often a Functor<T> is compared to a container holding instance of T where the only way of interacting with this value is by transforming it, with the map method. However in the functors API there is no standard way of unwrapping or escaping values from the functor; these unwrap implementations are usually quite specific to either the language and the frameworks employing them.

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.function.Function;

public class Identity<T> implements Functor<T> 
{
  private final T value;
 
  Identity(T value) 
  { 
    this.value = value; 
  }
  
  public T getValue()
  {
    return this.value;
  }
 
  public <R> Identity<R> map(Function<? super T, ? extends R> f) 
  {
    final R result = f.apply(value);
    return new Identity<R>(result);
  }
}

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 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 java.util.Optional starting from Java 8 is a functor with 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 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 empty() instance. In both cases, just like with Identity, FOptional is immutable and we can only interact with the value from inside. What differs FOptional 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 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 T -> R - but the behavior is much different. Now we apply a transformation on each and every item in the FList, declaratively transforming 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 invoke getAddress() 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 you java.util.stream.Stream 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 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 external event. But it will appear some time in the future. The mechanics of completing a Promise 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 Promise 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 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 not wait for the underlying customer promise to complete. Instead it returns another promise, of 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.

Shared axioms

Why are functors useful?

Functors generalize a variety of similar idioms like collections, promises, optionals, etc. with a single, uniform API that works across all of them, for example:

  • Identity
  • Result
  • Optional
  • List
  • Promise