λ Tony’s blog λ

Runar recently made mention of these so-called Functors and Monads in his excellent post about concurrency/actors in Java. There are all sorts of tutorials out there for understanding what a Monad is, however, I am of the opinion that one must first understand what a Functor is. This is because it is less complex and more general (all monads are functors plus more).

The Java Posse also made a couple of false claims about Runar’s article, but one in particular needs addressing. This is the notion that a functor is applicable to “Functional Programming”. This is false. A functor is applicable to programming. You really, really need to understand what a functor is, if you’re ever going to be skilled in any type of programming; even if it’s just Java web applications for the rest of your life. This concept does not exist ‘on the other side of the fence’ in the imaginary ‘functional programming world’. These suggestions are understandable of course and I don’t intend to labour the point — only make this point clear, since these apparent divides seem to pop up often. On with the story…

In Java, we have an interface called CharSequence. A few things can be said about CharSequence. How about:

All implementations guarantee that for some integer n, then if n >= 0 && n < length(), then charAt(n) will not throw an exception.

We might call this a law about CharSequence that all implementations must satisfy. We could even find other laws that must satisfy about implementations of the CharSequence interface.

A Functor is an interface and it has two laws. Sadly though, this interface cannot be expressed using Java’s type system — it is simply not clever enough. We must use a hypothetical Java to express it. First though, we have to make up for Java’s missing first-class functions by using an interface. This is easy:

interface Function<A, B> {
  B f(A a);
}

OK, so this a just an interface like any others. It needn’t satisfy any laws; it just takes an argument (A) and returns (B). We could write bazillions of implementations of this interface in Java. We’re going to need this interface to write the Functor interface.

Now, the missing part of Java is called higher-kinds — a term you needn’t concern yourself with too much. I hope this hypothetical syntax is enough to make the point clear:

interface Functor<E<_>> {
  <A, B> E<B> fmap(Function<A, B> f, E<A> fa);
}

So the foreign part here is E<_>. Consider E to stand for ‘Environment’. It is a type parameter that takes yet another type parameter (which is why it is denoted E<_>). This means I could use List or Set, but not Integer as the type parameter value for E, since List and Set take another type parameter while Integer does not. You might think of the Functor interface as ‘applying the given function within the environment’.

We might write an implementation like this:

class ListFunctor implements Functor<List> {
  public <A, B> List<B> fmap(Function<A, B> f, List<A> list) {
    // todo: apply the given function on all elements in 'list' and return the result
  }
}

In general discussion, we would call this the list functor, simply because the value for the environment has been applied. In Runar’s article, he was talking about the Callable functor; yet another environment. There are many possibilities for the environment here; List and Callable are but two.

The Laws

Let us not forget the laws Just like all implementations of CharSequence have laws to obey, so do all functors. They are called identity and composition.

Identity

Remember the Function interface? Here is an implementation:

class Identity<A> implements Function<A, A> {
  public A f(A a) { return a; }
}

If we are given an implementation of Functor — which I will call f — then it must satisfy f.fmap(new Identity(), x) is equivalent to x (for any value of x). So that’s the identity law out of the way. Mapping the identity function across a functor yields the same value.

Composition

The law of composition is a little less friendly when it comes to expressing it in Java so I will refrain While it is an important part of making up the concept of a functor, it may be best to defer this final piece of the puzzle for now.

For completeness, I will state the law using a shorter syntax, but if this is foreign or worrying, then please ignore it: f.fmap(a compose b, x) is equivalent to f.fmap(a, f.fmap(b, x)) (for any value of a, b and x — a and b are Function objects).

That’s all there is to a Functor. If you use the map function on lists or perhaps the map method on scala.Option, then you are using one specific instance of a functor, since these functions/methods satisfy the conditions for a functor. Even throwing an exception is using a specific functor! Perhaps that can be explained another time

I should also add that when referring to a functor (unqualified), we are referring to a covariant functor. Other types of functors include contra-variant and invariant functors. We can talk about those another day

Next: Just What the Flip is a Monad?

Questions?

In the spirit of yesterday’s post that denoted the Functor Laws using Reductio, I will also give the Monad Laws. Before I do however, here is an example use of the FunctorLaws object that runs 600 unit tests when testing a Functor implementation for scala.Option[A], scala.List and finally, for the scala.Either[A, _] functor just to make it a bit quirky and probably confuse a few of you (in that case, ignore it for now!)

  val prop_OptionIdentity = identity[Option, Int]
  val prop_OptionComposition = composition[Option, Int, String, Long]
 
  val prop_ListIdentity = identity[List, Int]
  val prop_ListComposition = composition[List, Int, String, Long]
 
  val prop_EitherIdentity = identity[Apply1Of2[Either, String]#Apply, Int]
  val prop_EitherComposition = composition[Apply1Of2[Either, String]#Apply, Int, String, Long]
 
  // OK passed 100 tests. (appears 6 times — once per property)

…and the obligatory Monad Laws follow (import statements omitted this time, but they are the same as previous)…

object MonadLaws {
  def leftIdentity[M[_], A, B](implicit m: Monad[M],
                                     am: Arbitrary[M[B]],
                                     aa: Arbitrary[A],
                                     ca: Coarbitrary[A]) =
    prop((a: A, f: A => M[B]) =>
      m.bind(f, m.unit(a)) === f(a))
 
  def rightIdentity[M[_], A](implicit m: Monad[M],
                                      am: Arbitrary[M[A]]) =
    prop((ma: M[A]) => m.bind((a: A) =>
      m.unit(a), ma) === ma)
 
  def associativity[M[_], A, B, C](implicit m: Monad[M],
                                           am: Arbitrary[M[A]],
                                           ca: Coarbitrary[A],
                                           cb: Coarbitrary[B],
                                           amb: Arbitrary[M[B]],
                                           amc: Arbitrary[M[C]]) =
    prop((ma: M[A], f: A => M[B], g: B => M[C]) =>
      m.bind(g, m.bind(f, ma)) === m.bind((a: A) => m.bind(g, f(a)), ma))
}

Woot! Woot!

A somewhat intricate and extremely useful code snippet using Reductio for testing the laws of any Functor instance (note that the Functor type is part of Scalaz):

import reductios.Property._
import reductios.Arbitrary
import reductio.Coarbitrary
import reductios.Arbitrary._
 
object FunctorLaws {
  def identity[F[_], A](implicit f: Functor[F], af: Arbitrary[F[A]]) =
    prop((fa: F[A]) => f.fmap((a: A) => a, fa) === fa)
 
  def composition[F[_], A, B, C](implicit f: Functor[F],
                                          af: Arbitrary[F[A]],
                                          ac: Arbitrary[C],
                                          cb: Coarbitrary[B],
                                          ab: Arbitrary[B],
                                          ca: Coarbitrary[A]) =
    prop((fa: F[A], h: B => C, i: A => B) =>
            f.fmap(h compose i, fa) === f.fmap(h, f.fmap(i, fa)))
}

Many people struggle to understand those fluffy things called Monads and why they are important. I’m not going to attempt to alleviate this to a large degree, but I have had a recent success with a friend in having them attempt to write a familiar Scala function as a method. That is, the List.flatten function, which simply takes a List of List of some type A and returns a List[A]. It does this by concatenating all the lists together. I think most people are familiar with this function and have a good mental model of how it works. If this is the case and you are less confident about List.flatMap, then I hope to bring a point to your attention that might help you bring it home.

If you take a look at List.sort, you see it takes a function (A, A) => Boolean. This is because the type parameter to List is ‘just any A’. It would be nice if it was ‘any A, so long as it has defined order’. That way, you can just call list.sort and be done with it. This would require the creation of a new class with a more restricted type parameter; for example, you might pass the function at list creation time, like you do with a TreeMap.

Imagine writing List.flatten on the List[A] class as a method using the same technique. You wouldn’t be able to, since the method belongs on a List[List[A]]. You’d need to write the method such that it takes an argument: A => List[A] before you could then call flatten. When you have a List[List[A]], you’d just call this method with the identity function x => x to obtain your resulting List[A]. Here is how the method would look:

def flatten(f: A => List[A]): List[A] = ...

Guess what?! This method is flatMap! Let’s ignore the fact that the Scala API is significantly broken, including the List.flatMap method using Iterable in place of List here. Notice though, that flatMap is actually generalised by taking another type parameter, so we have just invented an unnecessarily specialised version of flatMap. Let’s fix it:

def flatten[B](f: A => List[B]): List[B] = ...

Woot woot! In other words, flatten(list) is equivalent to list flatMap (x => x). Furthermore, this should hold for more than just list, but for other type constructors too (sadly, Option is missing a flatten function: Option[Option[A]] => Option[A]). This is a special relationship that all monads have (join is a synonym for flatten and bind is a synonym for flatMap):

join = bind id

We can express this using Reductio (the Scala API of course!):

val prop_flat = prop((t: List[List[Int]]) => List.flatten(t) == t.flatMap(x => x))
// OK passed 100 tests.

I hope this helps. If it doesn’t, ask a question or ignore my ranting

From http://www.news.com.au/comments/0,23600,23907216-462,00.html on the recent price rise by ABC Learning Centres (i.e. child care):

ABC Learing centres have now increased there fees three times since early 2007. There justification for these raises in no way benefit the children in they’re care or they’re staff!.

The Applicative Functor pattern is an incredibly powerful abstraction. I recently added it to a branch of Scalaz. However, it would be nice if I could alter the fixity of functions so that the parentheses below are not required to make the expression right-associative.

    val add = (a: Int) => (b: Int) => (c: Int) => a + b + c
    val none: Option[Int] = None // Grrr Scala
 
    // Some(24)
    println(Some(7) <*> (Some(8) <*> (Some(9) > add)))
 
    // None
    println(Some(7) <*> (none <*> (Some(9) > add)))
 
    // List(87, 88, 89, 91, 92, 93)
    println(List(1, 2, 3) <*> (List(77) <*> (List(9, 13) > add)))

Having to write that silly none value is annoying too. At the very least a none function would suffice:

def none[A]: Option[A] = None

That way. I could use none[Int] and be done with it.

Still, this pattern is a nice tool to use and I will surely be using it in the future.

(Copied from)

Wouldn’t it be nice if?

When disciplined programmers write unit tests, they often make reference to the fact that their tests provide a means of documentation the software that it is testing. This documentation is more appropriate than what would otherwise be informal and potentially ambiguous comments using English. Take the simple example of adding two numbers. We might document using informal language:

/**
 * Adds the two arguments.
 *
 * @param a Add this argument to the other one.
 * @param b Add this argument to the other one.
 * @return The sum of the two arguments.
 */

With unit tests, we might instead write something more formal and unambiguous:

assertEqual(add(2, 2), 4)
assertEqual(add(4, 3), 7)
... so on

It might be argued that both these forms of documentation complement each other. After all, while the unit tests have less room for misinterpretation, they are incomplete; for example, what about add(88, 37)? The English description makes up for this shortcoming.

We could reword our English to be a little more succinct:

/**
 * Passing 0 as one argument returns the other argument,
 * otherwise, the result is the same as subtracting 1 from one argument and
 * adding 1 to the other argument then passing those values instead.
 * e.g. add(2, 8 ) is the same as add(1, 9) and so on until one of the arguments reaches 0.
 */

Wouldn’t it be nice if we could express this formally in unit tests? You can, read on.

While this example is trivial, it scales in proportion to the amount of discipline that the programmer is willing to exercise by controlling side-effects in their program. If we write our programs such that most of our methods retain the property of referential transparency, we can use this advanced method of tests as documentation. When we refactor our code to make tests easier to write, it is often the case that we are doing exactly this anyway. Win win!

Let’s scale up a little

We’ll give a slightly less trivial example next, but not so trivial that it takes away from the important points. In fact, let’s unit test a specific part of the Java Collections library — the java.util.Collections.reverse method. There are various ways of testing this method and we will choose one here that serves to illustrate the point of unit tests as documentation.

The reverse method can be described as follows:

1. For the empty list, then reversing this list is always the same list
2. For the list with one element, then reversing this list is always the same list
3. For any other two lists (let’s call them ‘a’ and ‘b’), then appending b to a then reversing will yield the same list as reversing a, then appending the result to the reverse of b. Since this statement is a little convoluted, let’s write it with some pseudo-Java syntax notation: (a.append(b)).reverse() == b.reverse().append(a.reverse())

It is an interesting observation here that we have completely specified the reverse method. That is, under some reasonable assumptions, it is not possible to write a method that is not equivalent to reverse that also satisfies our statements above. This is the ultimate form of code documentation!

We will ignore the first statement for the sake of interest and verbosity and focus on expressing the other two. This is because statements 2 and 3 have free variables, while statement 1 is merely an assertion that does not illustrate any interesting points. Let us start with the second statement and articulate it using Reductio:

Property p2 = property(arbInteger, new F<Integer, Property>() {
  public Property f(Integer i) {
    return prop(single(i).equals(reverse(single(i))));
  }
});

That pretty much sums up statement 2 doesn’t it? What about statement 3:

Property p3 = property(arbLinkedList(arbInteger), arbLinkedList(arbInteger), new F2<LinkedList<Integer>, LinkedList<Integer>, Property>() {
  public Property f(LinkedList<Integer> a, LinkedList<Integer> b) {
    final LinkedList<Integer> x = reverse(append(a, b));
    final LinkedList<Integer> y = append(reverse(b), reverse(a));
    return prop(x.equals(y));
  }
});

Is that it?

Yep. Notwithstanding the absence of statement 1, we have completely specified the behaviour for the Java Collections.reverse method. We have exhaustive and formal documentation instead of one or the other as we traditionally do. What an improvement!

Yeah but I want to unit test it too

That’s not hard either. How many unit tests do you want to run? By default, Reductio will run 100 unit tests per Property declaration. You can adjust this and various other factors about how your unit tests are executed. If you want to take the default, then a few more lines of code are enough to do just that:

list(p2, p3).foreach(new Effect<Property>() {
  public void e(Property p) {
    summary.println(p.check());
  }
});

If you run this line of code, you will see the result of your 200 unit tests on the standard output:

OK, passed 100 tests.
OK, passed 100 tests.

Is that too magical for you? Don’t believe me? Want to see it fail? OK, let’s fail it. In the expression of statement 3, change the line b.addAll(a) to a.addAll(b) and run again. What did you see? Here is what I saw:

OK, passed 100 tests.
Falsified after 4 passed tests with arguments: [[3, 2, -3, 4, -3],[2, -3, 4, -3]]

Yep, it failed alright When those two list values are used as our free variables, the property is false and the unit test fails.

Other Resources

• A Case for Automated Testing
• Reductio EqualsHashCode
• Reductio Website
• More Reductio examples
• Reductio Manual

Complete Runnable Source Code

import fj.Effect;
import fj.F;
import fj.F2;
import static fj.data.List.list;
import static reductio.Arbitrary.arbInteger;
import static reductio.Arbitrary.arbLinkedList;
import static reductio.CheckResult.summary;
import reductio.Property;
import static reductio.Property.prop;
import static reductio.Property.property;
 
import java.util.Collections;
import static java.util.Collections.singletonList;
import java.util.LinkedList;
 
public class ListReverse {
  public static void main(String[] args) {
    Property p2 = property(arbInteger, new F<Integer, Property>() {
      public Property f(Integer i) {
        return prop(single(i).equals(reverse(single(i))));
      }
    });
 
    Property p3 = property(arbLinkedList(arbInteger), arbLinkedList(arbInteger), new F2<LinkedList<Integer>, LinkedList<Integer>, Property>() {
      public Property f(LinkedList<Integer> a, LinkedList<Integer> b) {
        final LinkedList<Integer> x = reverse(append(a, b));
        final LinkedList<Integer> y = append(reverse(b), reverse(a));
        return prop(x.equals(y));
      }
    });
 
    list(p2, p3).foreach(new Effect<Property>() {
      public void e(Property p) {
        summary.println(p.check());
      }
    });
  }
 
  static <A> LinkedList<A> single(A a) {
    return new LinkedList<A>(singletonList(a));
  }
 
  static <A> LinkedList<A> reverse(LinkedList<A> as) {
    LinkedList<A> aas = new LinkedList<A>(as);
    Collections.reverse(aas);
    return aas;
  }
 
  static <A> LinkedList<A> append(LinkedList<A> as1, LinkedList<A> as2) {
    LinkedList<A> aas = new LinkedList<A>(as1);
    aas.addAll(as2);
    return aas;
  }
}

(Copied from)

Discipline and Testing

Disciplined programmers write tests while developing code. Some even refactor their tests when certain situations arise. Imagine this one. You have just written a method that takes two integer arguments, adds them and subtracts seven before returning the result.

Your code might look like this:

int addThenSubtract7(int x, int y) {
  return x + y - 7;
}

When you test this code — either before, during or after you write the method above — you will likely write tests that exhibit some property about the method under test. For example, when one argument is the negation of the other, you will always get back -7.

assertEquals(-7, addThenSubtract7(0, 0));
assertEquals(-7, addThenSubtract7(1, -1));
assertEquals(-7, addThenSubtract7(2, -2));
assertEquals(-7, addThenSubtract7(3, -3));
assertEquals(-7, addThenSubtract7(4, -4));
assertEquals(-7, addThenSubtract7(5, -5));

You might refactor in this scenario:

assertTrue(negationBecomesNegative7(0));
assertTrue(negationBecomesNegative7(1));
assertTrue(negationBecomesNegative7(2));
...
 
public boolean negationBecomesNegative7(int a) {
  return addThenSubtract(a, -a) == -7;
}

Indeed, you might use a loop for your input values:

for(int i = 0; i < 100; i++) {
  assertTrue(negationBecomesNegative7(i));
}
 
...

Specifying Properties

There are other properties about the method addThenSubtract7. For example, if you switch the arguments, the result is unaffected. In fact, this property comes up a fair bit so it even has a name; commutativity. You could come up with a similar scenario as that described above through a process of repeating assertions with different values, refactoring a bit and generally trying to test as rigorously as possible with minimal effort and permitting future maintainability of both your code and your tests.

Eventually, you will have written properties about your method such that there is no reason to write any more properties, since they would be implied by your existing properties. For example:

• You could write a test for addThenSubtract7(0, anyValue) results in anyValue - 7.
• Then you could write a test for commutativity; addThenSubtract7(someX, someY) results in the same value as addThenSubtract7(someY, someX).

Now, is there any point writing a test for addThenSubtract7(anyValue, 0) results in anyValue - 7? Isn’t this implied by the test for commutativity? Right, this test would be redundant.

Ultimately, you could aim for an unambiguous specification of your method under test. However is there a nicer way to write all these tests?

Let’s Automate it!

Going back to the first property negationBecomesNegative7, don’t you really just want to say this and then let the rest be taken care of by clever automation?

for all int values named a. then addThenSubtract7(a, -a) == -7

This is the job of Automated Specification-based Testing such as that which is implemented by Reductio for Java. Reductio allows you to write the above expression using standard Java syntax:

Property p = property(arbInteger, new F<integer, Property>() {
  public Property f(final Integer a) {
    return prop(addThenSubtract7(a, -a) == -7);
  }
});

What is going on here? We are passing in our generator of arbitrary integer values (arbInteger), then an anonymous inner class that asserts our property for our free variable (the one called ‘a’).

OK, it can’t be this easy can it? No, sorry, it can’t. There is an enormous of work to do next. Ready, here it is:

p.check();

With all that heavy lifting taken off you by the test automation, you should now have plenty of time and energy to get on with delivering your software to your client or maybe reading news blogs if that is what you prefer

Shrinking

When you run the test automation, you receive a result of success after running 100 (by default — adjustable of course) tests or you receive a failed result with a counter-example. That is, you receive a value for your free variable (a) for which the property was not true.

Does it stop here? I mean, this is great and everything, but surely there’s not more help that can be provided by clever test automation software? There are a couple more clever things that can be done.

First is the shrinking of a counter-example. Imagine there was a bug in the addThenSubtract7 method and you received a counter-example of 1789234. What’s so special about this number? Well, that depends on the bug, however, maybe this is just the first counter-example that was found. Imagine, however, that the bug also exhibited itself (i.e. the property fails) with a counter-example of 2. Isn’t this a more useful counter-example? Wouldn’t you prefer that this one was reported and not that big, insignificant number?

So that’s another great feature of test automation; it can report back to you useful counter-examples in the event of a bug. When you perform manual testing as above, you might remove a couple of your assert methods to help narrow down the bug. This is the hard way! This very act can be automated.

Imagine you wrote this property (a + b == a - b):

final Property p = property(arbInteger, arbInteger, new F2<integer, Integer, Property>() {
  public Property f(final Integer a, final Integer b) {
    return prop(a + b == a - b);
  }
});

It turns out that this property is true for some values such as a == 0 and b == 0, but false for others:

• a = 1, b = 15
• a = 147, b = 92582
• a = 5923, b = 12

But which of these counter-examples is going to be most useful to you, the tester? Any of the above? How about this counter-example: a = 0, b = 1? Isn’t this more useful to you than any of those above?

Good test automation software will report a reasonably small counter-example in the event of the falsification of a property.

Automated Mocking

OK, is there more? Yes sorry to keep your attention. Test automation software will also generate instances of an interface for you. That’s right, you can quantify across an interface in your property expressions. This is a bit like mocking, except not so manual; you just pass in the arbitrary generator (Reductio provides them of course) just as we did above and you can wipe your hands clean of the remaining manual effort otherwise.

You might want to write a property where you say something like, “for all instances of my interface or class, then such and such…”. This might be an instance of the HttpServletRequest interface or perhaps one of your own classes. The good part is, no more manual mocking.

Want to Learn More?

You can read the Reductio Manual or perhaps look at some code examples. If you’re a fan of the coming Java 7 BGGA closure syntax, you might prefer these code examples. Perhaps you’re into higher-level programming and prefer Scala code examples. Whichever you choose, please feel free to jump on the Reductio mailing list or chat channel and ask your question, no matter how silly it seems to you.

Re: Your insistence on distinguishing unit testing and integration testing.

You make the distinction between unit testing and integration because you are a sloppy programmer. You throw side-effects around like a 5 year old in a play pen. You do not care for intellectual discipline in your thinking process. Nor do you care for high-level abstraction or composition of your software. Instead, you insist on this dogmatic “test driven” nonsense. You do this because you are married to the FORTRAN family of programming languages. Your so-called integration tests exist because you have implicit free variables in your equations like a ‘good little imperative programmer’. If you did decide to apply discipline and consider your side-effects, you’d see no distinction between unit testing and integration testing. I realise that this possibility escapes your feeble and narrowed mind at this stage of the socratic midwife process.

When you do unit test, you’re using an awfully impoverished method. I mean, “assert this and assert that”. Give me a break! You think this is going to “drive” something? Anything? OK, it drives me bonkers to think that you insist on spreading mythological, pseudo-scientific, fanatical bullshit (excuse the term, but it is most accurate) and have followers repeat said myths in such an obedient I-cant-think-for-myself fashion. You think you’re contributing to the “design” and “quality” of your software? How mistaken you are and what empathy I feel for you.

I implore you to retract your silliness and take seriously the charge that you are a sloppy programmer (evidence forthcoming). Your dependence on “agile this” (I play A grade squash, I’m perfectly agile, thanks) and “test drive that” are entirely dependent on an existing sloppy form of programming. Furthermore, these workarounds not only rest on a flawed premise, but they are extremely diluted anyway. Even with the given silly premise you can significantly improve! But I won’t tell you how, no not yet. First you must prepare for an act of apostasy, which I understand can be very traumatic. So I can’t help you until then, but in the meantime, I kindly ask that you stop imposing your silly ideas on me, because yes, they are silly.

See you on the other side.