Applicative Programming 3

prev next

Functors and Monads

The word monad was mentioned in the previous part; there even was a definition, but rather loose.

Different people come up with different definitions of a monad; computer science people hurry to produce their "better definition", being too impatient to read the one that has been there for about 40 years now. This is like medicine; if we don't like our pills, we may switch to alternative medicine, at times with fatal consequences.

I see no reason to study the "alternative", "computer" Mathematics. There's just one... more or less.

So, I am going to rephrase the right definitions in our specific context. Further on I will be using Scala, since Java type system is too weak.

Functor

Say we have a parameterized type Т[_] (with one parameter); this provides a type T[X] for each individual type X. This type transformation is called a functor when the following conditions are satisfied:

• for each function f: X → Y a function T(f): T[X] → T[Y] can be produced. This operation, getting a T(f) for an f, is usually called map (in Haskell, in Scala, in Functional Java) or transform (C++, Google's Guava library for Java).

• this operation (defined above) preserves the identity function: that is, if we take identity[X]: X → X, then T(identity[X]) will be equal to identity[T[X]]. (I won't discuss here the issue of equality for functions.)

• this operation preserves the composition of two functions: that is, if we have f: X → Y and g: Y → Z, and the function h = f.andThen(g): X → Z, we will have T(h) = T(f).andThen(T(g)): T[X] → T[Z].

Generally speaking (there's a caveat, will return to it later), some parametric types are functors, some not.

Say, Class[T] is not a functor: we can have a function f: X → Y, but this does not provide us with a function Class[X] в Class[Y].

On the other hand, for Scala's List[_] class, each f: X → Y gives us a transformation from a list of type List[X] to a list of type List[Y], just by List[X].map(f) - this gives us the operation we were looking for, f ↦ List[X].map(f).

(** Important Notation Remark. The arrow ↦ is used to denote the fact that a specific value to the left is mapped to a specific value to the right. E.g. we can define a function plus_one: x ↦ x + 1 - an x is mapped to x+1. If we deal with sets, the collection of such mappings, one per each element of a set, uniquely specifies a function (by Set theory axioms).

Monad

A monad is a functor T with two collections of functions (already mentioned in the previous part), namely:

• unit, u[X]: X → T[X], it can be also called pure, or (in Haskell), return.

For lists, this is a singleton list constructor. For other monads... well, we'll get back to it later.

Note. It is not enough that we specify arbitrarily a function for each type X; it should also behave properly relative to map.

This means that, given a f: X → Y, we can get from X to T[Y] via two ways: one through Y, ; the other through T[X], . These two paths (that is, the two functions produced by these two paths) should be equal. In Category theory this is depicted as a commutative square:

• multiplication m[X]: T[T[X]] → T[X]. Also known as join and flatten.

The latter term, flatten is illustrated by the way it is done with lists: we take a list of lists and pull it into one single linear list.

Multiplication too should comply with the naturality law; I won't write it down here; it is similar to the one for unit.

Monad Laws

It is not enough to have two functions with given signatures; there are rules.

1. Multiplication must be associative: T[T[T[X]]] → T[T[X]] → T[X] can be produced in two ways; the result must be the same. E.g. a list of lists of lists can be flattened by either first flattening the external, then flattening the result, or flattening each element of the internal LoL, then flattening the result.

2. Unit must be a neutral element for multiplication, both left and right: T[X] → T[T[X]] → T[X] - we can have two such functions; both must be equal to identities.

E.g. for lists, there are two ways to map List(x) → List(List(x)); but then after we flatten List(List(x)) and produce List(x), the function is the same.

(Now the philosophical question of what we mean by equality is lurking again. Well, let's assume we have a jvm inside, and each type has equality defined, which, scientifically speaking, is probably not an equality but an isomorphism.)

Examples

There are lots of known examples: List, State, Maybe (Option), Set (covariant version), Environment, Read, Continuation... We are not going to cover them all. Let's take List, Option, Set (these are pretty known both in Java and Scala), and Exception, a secret monad, of the kind which Erik Meijer called the hidden implicit monads that every language has.

List

Here a singleton list constructor plays the role of unit, and flatten plays the role of multiplication. List is the most favored monad; it's like a guinea pig for experimenting with monads.

Option

Unit is defined as the constructor x ↦ Some(x); multiplication consists of flattening (Some(Some(x)) ↦ Some(x), the rest maps to None).

Set

This monad is trickier. There exist two Set functors, visually indistinguishable. I'm talking about this one:

Given an f: X → Y, we define Set(f) like this:

(s: Set[X]) ↦ Imagef(s) = {(y:Y)| s.contains(f-1(y))}.

In plain words, each set s of elements of type X is mapped to its image produced by function f.

Unit is defined by singleton set constructor. Multiplication (defined on a set of sets of elements of type T) is defined as a union:

(ssx: Set[Set[T]]) ↦ ∪{sx | ssx.contains(sx)}.

Exception

To talk about exception as a monad, one has to go beyond the limits of a given programming language, or model it, adding another level if indirection, the trick that solves every individual programming problem (there's no constructive solution for all programming problems... within the theory of programming problems, of course).

Specifically, if we have a function that can throw an exception, or can return a result, let's imagine it returns a container that can throw an exception on content retrieval, something like this:

    trait Exceptional[T] { def apply(); }
      case class Ok[T](value: T)       extends Exceptional[T] { def apply = value }
      case class Oops[T](x: Exception) extends Exceptional[T] { def apply = throw x }

We can easily build a monad out of it, very similar to Option[T]; multiplication is defined like this:

    def m[T](eet: Exceptional[Exceptional[T]]): Exceptional[T] = eet match {
      case Ok(et) => et // just extract the content which is an Exceptional anyway
      case ex     => ex // it's the same exception
   }

Now back to reality, and let's see how is it in practice. If a function calls another function, and that function can throw an exception, this exception (unless we catch it) is passed up as if we were throwing an exception. Or we don't throw an exception; then the result is returned.

That's it for this part; further I'm going to tell about what is the problem if we have monads all around; how these problems are being solved in some languages, why they are unresolvable in general case, and what we can do about it.

prev next