The state monad in Java 8, eventually…

This is no tutorial about the state monad and I’d be foolish if I hoped to use all these convoluted snippets of strongly-typed generics-laden Java code to show the monad’s beautiful essence to someone who hasn’t yet caught at least a glimpse of it elsewhere. On the other hand, what I present here is a non-trivial case that in its original C# version has taught me a lot about handling problems using this monad.

The code is available on GitHub with project name BeckmanStateMonad.

This implementation reaches as of today the following goals:

  • show a Java 8 implementation of a state monad
  • make the monad instance chainable through its instance method bind, avoiding static binary methods as much as possible
  • port in Java the C# example of monadic labeling of a binary tree, prepared by Brian Beckman for Channel9 subscribers [1]
  • illustrate a few very simple cases of chainable state monad
The string-labeled tree on the left is transformed into a tree of state-content pairs. The state bit is an increasing integer, while the content is the original label.
The string-labeled tree on the left is transformed into a tree of state-content pairs. The state bit is an increasing integer counter, while the content is the original label. The example at [1] is truly precious, as it shows two different ways to perform the modification of the tree:
1) in the first way (non monadic) one is forced to explicitly pass the int counter as parameter through the recursive calls of the tree-traversing function. See ManualLabeling.java
2) afterwards [1] shows how the monadic tree-traversing function passes recursively the sole branches and leaves of the tree, as the evolving state remains embedded and transparent inside the monad containers. See MonadicLabeling.java

Future goals (if time will permit) are the following:

  • create a useable sandbox environment for my experiments with typed monads and monad transformers
  • illustrate a few examples of how the state monad must be used to solve real-life problems, threading state through the computation whilst mutating it

A list of references for understanding the ins and outs of the state monad is provided at the end of this post.

About this implementation – its strong and weak points

Organisation of the classes

The pair (state,content) is represented by a Scp<S,A> object.

The StateMonad class is therefore a container for a canonical function with type signature:

S -> Scp<S,A>

Each state monad is an instance of the StateMonad class and is provided with a bind instance method to chain it with functions capable of pulling out its content and using that to build a new state monad.

Unit (aka return) is implemented as a static method for the whole class.

Other accessory methods like getState and putState will possibly be added in the future.

I have intentionally avoided to impose a Monad generic interface or an abstract supertype because in my experience this just goes in the way of writing maintainable code. Monads are pretty much isolated idioms; you may want to use a Maybe (pardon me, an Optional) here, you may want to use a State there, but the fact that both obey to some general laws and fulfill some accordingly imaginable generic API won’t make your code any more readable or flexible.

This may change when I’ll port to Java the knowledge I’ve built about monad transformers, so to use several monads in the same computation. But until that day I’ll stick to the rule of simplicity.

Test cases

The tree is defined as an abstract Tr<A> class, whose instantiable components are Lf<A>(A content) leaves and Br<A>(Tr<A>left,Tr<A>right) branches

Monadic tree labeling

This procedure transforms a tree according to the image at the top of this post.

Left we have a Tr<String>, at the right we have a Tr<Scp<Integer,String>>. The right tree is produced by the run of the state monad prepared by the Mkm(Tr<String> t) method. As it is customary with this monad, we provide an initial state new Integer(0) and retrieve a (watch carefully!):

Scp<Integer,Tr<Scp<Integer,String>>>

This is kinda confusing. Class Scp was absolutely necessary and it has been created because every state monad on this planet always returns a state-content pair once provided with a state. Incidentally in this case the same Scp class is used also to label the leaves of the processed tree. It could have been enough to swap the strings “a”, “b”, “c” with the integers 0, 1, 2 and pass from a Tr<String> to a Tr<Integer> but the author of the example chose instead to label the new tree with pairs. Fair enough…

Anyway, once we have retrieved the state-content pair from the monad run, we extract its second term and there we have the right tree with the new leaves.

The mechanism that substitutes a Lf("b") with a Lf(new Scp<Integer,String>(new Integer(1),"b")) and updates the state ready for the next leaf is worth spending a few more words.

Juggling state and content during the preparation of the monad

We are inside a recursion of MkM, exploring either the left or the right subtree of a branch of the input tree; we are building the state monad of the output subtree (that’s a function that will return a (state,subtree) pair) and we discover that the input subtree is a leaf. What are we to do? We know that the state (an Integer) will flow through this point when the completed monad will be run; we need to grab it, use it as a value to label the output leaf in the monad and pass it on as the new state, increased by 1. That’s the job for a custom-built StateMonad<Integer,Integer> aptily called updateState and whose canonical function looks like this:

n -> (n+1,n)

Here the usual s variable is renamed n, because all this makes sense only for ints. For other types of state, this operation may be different; for example the incoming state may be read to provide some useful value and in the meantime it may be enriched with a new key-value pair coming from some encoding operation. The whole point is that the incoming state feeds both the state and the content into the next step.

So, how does the next computation look like? It will be a function that takes as input the ‘n’ value and returns a state monad carrying inside implicitly whatever state we are passing (we know this is gonna be n+1 but the magics of the state monad keep all this hidden) and the modified leaf as content. In other words, the next computation is of type

Integer -> StateMonad<Integer,Tr<Scp<Integer,String>>>

A function with this signature is the perfect argument for updateState.bind and shifts the computation from generic type A = Integer to generic type B = Tr<Scp<Integer,String>>

The details of the creation of the output leaf are to be found in the code. Please note that, because of the issues presented in the next paragraph, I am not using unit to return the freshly built monad, but I am composing a whole s -> (s,a) canonical function and feeding it to the StateMonad constructor.

Improvable parts

I started this pet implementation of the state monad in Java 8 hoping lambda’s would allow me to simplify enormously the boilerplate. This goal hasn’t been met to my expectations.

I believe this is mostly due to insufficient support for @FunctionalInterface‘s by the compiler. I planned to use a

java.util.function.Function<S,Scp<S,A>> s2scp

at the heart of the monad and be able to run it with

monadInstance(state)

or at least with

monadInstance.s2scp(state)

In the reality, as soon as bind was involved I have been forced to invoke explicitly the apply method of Function, the same obnoxious thing that was mandatory with the previous versions of the language.

There are a few points where anonymous lambda’s take a place on the stage; but in order to assist the compiler in matching the types from the generic <S,A,B> in the StateMonad class definition, they have to be so strongly and carefully typed that the syntax becomes real, real clumsy.

Again due to compiler complaints(*), I have been so far unable to make meaningful usage of the static method StateMonad.UNIT, both as:

  • first-order object inside e.g. the demonstration of the second monad law
  • constructor to return specific state monad instances (I have to manually build a StateMonad instance providing the s->(s,a) function myself)

(*) I am reasonably convinced this is a teething problem of the compiler, because the same construction runs flawlessly in Scala

Of course I may be wrong and I’ll be glad to improve my implementation using feedbacks from anyone.

References

[1] – http://channel9.msdn.com/Shows/Going+Deep/Brian-Beckman-The-Zen-of-Expressing-State-The-State-Monad
[2] – https://faustinelli.wordpress.com/2013/08/14/handling-io-with-the-state-monad-in-javascript/
[3] – http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/
[4] – http://www.slideshare.net/dgalichet/scalaio-statemonad

Advertisements

One thought on “The state monad in Java 8, eventually…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s