DRAFT DOCUMENT
Contents
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:
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 |
---|
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 newfunctor
with the transformed values, leaving the originalfunctor
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 tomust 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.
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 newfunctor
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.
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
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
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
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
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
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