Write You a Monad for No Particular Reason at All!
TL;DR Writing functional programming library in Java
Functional Programming paradigm and languages that fully utilize it’s benefits are slowly gaining popularity nowadays not only in academia but also in enterprise becoming de facto standard for future generations of programmers. Maybe in 10 years from now humanity will come up with a better idea of how to make bug-free quality software that does the job and takes less effort to produce, however currently we are living in a century of Object Oriented programming systems slowly morphing into Functional Programming systems. There are a lot of learning resources on internet about Function Programming in general and Functional Languages such as Haskell, Erlang, Scala, Clojure and many other. You all probably heard about Learn you a Haskell for Great Good book, a really bright, colorful and interesting book that got me into Haskell programming few years ago. Some of you may even tried reading it. I think most of people without prior functional programming experience that start reading it sooner or later hit a bottom of their mental capacity while trying to comprehend Monads. This article is intended for this people! Yes this post is all about Functors and Monads you heard it right! In order to explore the ideas of functional programming let’s create a small functional programming library in Java that will have Functors and Monads and by doing so learn about functional programming from a really unusual perspective of using Object Oriented programming. Our target compiler will be Java 6 (yes we won’t be using new fancy Java 8) as most of the people that are reading this now are probably more familiar with it rather than newer version. For those of you who are too lazy to follow can check the whole thing at my fpj repository, however I strongly encourage you to try reimplement it all by yourself from scratch. The information described in this post implies that you have prior experience or basic understand of Monads but want to better understand them internally. So let’s get to work!
First of all let’s start with key concept of functional programming, a function. A function is something that takes A and produces B by a process called application of function. Let’s implement it in Java using generic interface. Basically any object that implements that interface can be considered a valid function.
12345
publicinterfaceFunction<A,B>{Bapply(finalAa);}
A predicate is a function that takes A and produces boolean value.
Wait what if we don’t need to produce any result or have any argument what we should do then? A Unit is an object that represents exactly this or simply nothing.
What if we need to take more than one object and produce more too? That’s what a Tuple is for. You can even use Tuple to combine more than two objects by putting a Tuple inside another Tuple.
publicclassTuple<A,B>{privateAa;privateBb;publicstatic<A,B>Tuple<A,B>tuple(finalAa,finalBb){if(a==null)thrownewIllegalArgumentException("first argument has no value");if(b==null)thrownewIllegalArgumentException("second argument has no value");returnnewTuple<A,B>(a,b);}privateTuple(finalAa,finalBb){this.a=a;this.b=b;}publicAfirst(){returnthis.a;}publicAgetFirst(){returnthis.a;}publicBsecond(){returnthis.b;}publicBgetSecond(){returnthis.b;}}
Now let’s discover a way of how to use functions. Let’s define a helper class called Functional and put some static methods into it. The functions we are going to write are so simple and common that any functional programmer can’t live without them. First of all what can we do with functions? Yes definitely we can combine a function with another function so basically if we have a function that takes A and produces B, and we have a function that takes B and produces C we can combine this two into a function that has a following type description A–>C (following from here we’ll be using a short notion of A–>B to describe a function that takes A and produces B).
What else can we do with functions? Yes, exactly we can map them over a Collection of objects and produce a Collection of results.
So if we have a function A–>B and a Collection of A objects we can map it over that Collection to produce resulting Collection of B objects.
We can also fold a value over collection using a function. So basically if we have initial value of A, Collection of B and function that takes A–>B–>A we can fold it over by
applying the function to an initial value and first object in Collection and then repeating the process with the result of this application with the rest of the Collection objects.
In functional programming this is usually called left fold.
Now let’s explore another way of making a function that takes several arguments and produces a result.
We can use Tuple for this however sometimes it’s easier to define it more simpler like this.
This definition is interchangeable with definition of Function<Tuple<A,B>,C> so we can make a helper method in Functional class that can take a function that takes a Tuple and produce Function2 if needed and vice versa.
We can also delay the application of an argument to a function by creating another function that takes Unit instead of the argument. This concept is usually called lazy function.
And finally we can do the same folding we did previously only starting from the last element of the Collection instead of the first. This is called folding from the right or simply right fold. We can make use of previously defined foldLeft method and Java’s ListIterator and flip helper method we defined earlier to do that easily.
Now all this is cool and interesting but wait didn’t we said at the beginning that this post is about Functors and Monads. Sure we did so let’s start exploring these concepts!
First of all what is a Functor? A Functor<A> is some object that contains A and you can apply a function of type definition A–>B to. This transforms it into another Functor<B> that contains result of that application, B value. For example we can consider a Collection<A> to be a Functor<A> because we can apply a function of A–>B over all objects of that Collection and have a Collection<B> of results of that application. Simple? Yeah well not really that simple as it may sound however you’ll understand it eventually I hope.
But what about Monad? Well the concept of Monad is really close to the concept of Functor. Monad<A> is some object that contains A that can be transformed into Monad<B> by application of function of type definition A –> Monad<B>. In functional programming this is called monadic bind. Also if we have B value we can transform it into Monad<B>. This is called return but in our framework we’ll name it shortly ret because return is Javakeyword which can’t be used for a method name. But that’s not all there is more! Any Monad is a Functor too our Monad interface will extend Functor interface!
Now we have a base for our functional programming framework. Let’s write some monads to better understand the concepts behind it. But before we do that let’s define some base abstract class
that will have one another kind of monadic bind method that can be used on any Monad<A> binding it to a Monad<B> just by specifying the Monad<B> itself instead of function. Also we can use Function<A,B> for monadic bind too by combining it’s result with ret, this method we will call liftM!
Let’s write our first Monad. It’s called Maybe<A> and it can either contain A value or be empty! As you can see we need some methods in order to look inside this Monad and check if it contains a value or not! Also we’ll need to implement fmap method for it to be a Functor and bind and ret methods for it to be a Monad! Implementing fmap is simple, we simply look into the Monad if it contains a value we apply provided function to this value, if not then we just return empty Maybe<A> monad. Same with the bind method but we don’t need additional step of creating a Maybe<A> monad as the provided function returns it!
publicclassMaybe<A>extendsAbstractMonad<A>{privateAa;privatestaticfinalMaybenothing=newMaybe(null);publicstatic<A>Maybe<A>just(finalAa){if(a==null)thrownewIllegalArgumentException("argument has no value");returnnewMaybe<A>(a);}publicstatic<A>Maybe<A>nothing(){return(Maybe<A>)nothing;}privateMaybe(Aa){this.a=a;}publicAvalue(){if(this.a==null)thrownewIllegalStateException("has no value");returnthis.a;}publicAgetValue(){if(this.a==null)thrownewIllegalStateException("has no value");returnthis.a;}publicbooleanisNothing(){returnthis.a==null;}publicbooleanhasValue(){returnthis.a!=null;}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){if(isNothing()){returnMaybe.nothing();}else{returnf.apply(this.value());}}public<B>Monad<B>ret(finalBb){returnMaybe.just(b);}public<B>Functor<B>fmap(finalFunction<A,B>f){if(isNothing())returnMaybe.nothing();elsereturnMaybe.just(f.apply(this.value()));}}
Now that we have Maybe monad we can implement another method in Functional class called find. Basically what find does is that it takes some Predicate function and a Collection of objects to check this predicate
and it returns the first element of that Collection for which the Predicate returns true. If for all elements the Predicate is false it returns empty Maybe monad.
Next is Either<A,B> monad. This monad contains either left A or right B value. This can be used to propagate exceptions or be used in any case where you need to either return one value or another but not both at the same time. Note this is Monad<B>. This code is almost identical to Maybe<A> but instead of
returning empty value we return the monad itself since in the case of left value it can be considered a Either<A,C> monad.
publicclassEither<A,B>extendsAbstractMonad<B>{privateAa;privateBb;publicstatic<A,B>Either<A,B>left(finalAa){if(a==null)thrownewIllegalArgumentException("argument has no value");returnnewEither<A,B>(a,null);}publicstatic<A,B>Either<A,B>right(finalBb){if(b==null)thrownewIllegalArgumentException("argument has no value");returnnewEither<A,B>(null,b);}privateEither(Aa,Bb){this.a=a;this.b=b;}publicbooleanisLeft(){returnthis.b==null;}publicbooleanisRight(){returnthis.a==null;}publicBright(){if(this.b==null)thrownewIllegalStateException("is not right");returnthis.b;}publicBgetRight(){if(this.b==null)thrownewIllegalStateException("is not right");returnthis.b;}publicAleft(){if(this.a==null)thrownewIllegalStateException("is not left");returnthis.a;}publicAgetLeft(){if(this.a==null)thrownewIllegalStateException("is not left");returnthis.a;}public<C>Monad<C>bind(Function<B,Monad<C>>f){if(isRight())returnf.apply(this.right());elsereturn(Monad<C>)this;}public<C>Monad<C>ret(Cc){returnEither.right(c);}public<C>Functor<C>fmap(Function<B,C>f){if(isRight())returnEither.right(f.apply(this.right()));elsereturn(Functor<C>)this;}}
Next is a Reader<A>Monad. This Monad is usually used to propagate immutable piece of data such as configuration across your code. It’s an interesting case to implement. We could implement it using a Tuple<E,A> however it’s traditionally implemented as Function<E,A>. In order to get E value we implement ask method. For the rest of the methods we usually call runReader() and then apply E value to them. This way we propagate the E value across binded Reader monad’s safely.
publicclassReader<E,A>extendsAbstractMonad<A>{privateFunction<E,A>f;publicstatic<E,A>Reader<E,A>reader(finalFunction<E,A>f){if(f==null)thrownewIllegalArgumentException("argument has no value");returnnewReader<E,A>(f);}privateReader(finalFunction<E,A>f){this.f=f;}publicFunction<E,A>runReader(){returnthis.f;}publicReader<E,E>ask(){returnnewReader<E,E>((Function<E,E>)Identity.identity());}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){returnnewReader<E,B>(newFunction<E,B>(){publicBapply(finalEe){return((Reader<E,B>)f.apply(runReader().apply(e))).runReader().apply(e);}});}public<B>Monad<B>ret(finalBb){returnnewReader<E,B>(newFunction<E,B>(){publicBapply(finalEe){returnb;}});}public<B>Functor<B>fmap(finalFunction<A,B>f){returnnewReader<E,B>(newFunction<E,B>(){publicBapply(finalEe){returnf.apply(runReader().apply(e));}});}}
Before implementing next Monad let’s explore another concept of Functional Programming called Monoid. Basically Monoid is some entity that can be empty or non-empty and can be appended to another Monoid. Appending empty Monoid to non-empty Monoid gives you the same non-empty Monoid. Simplest example of Monoid are natural numbers. In case of natural numbers we can consider zero as empty Monoid and any non-zero number to be non-empty Monoid and operation of appending two Monoids to be addition of natural numbers. Let’s write an interface of Monoid
Before we continue implementing monads let’s implement one example of Monoid. First we’ll define an AbstractMonoid class that will have some additional methods called mconcat for mappend-ing List or Collection of Monoids starting from an empty Monoid.
And now we are ready to implement ListMonoid which is basically a linked list of nodes that are either empty or contain a value and reference to next list node.
This implementing is ugly due to lack of TCO in Java, however it’s not too complex and just repeats any linked list implementation in Java or any other
programming language.
publicclassList<A>extendsAbstractMonoid<A>implementsFunctor<A>{privateAhd;privateList<A>tl;privatestaticfinalListempty=newList(null,null);publicstatic<A>List<A>list(finalAhead,finalList<A>tail){if(head==null)thrownewIllegalArgumentException("head has no value");if(tail==null)thrownewIllegalArgumentException("tail has no value");returnnewList<A>(head,tail);}publicstatic<A>List<A>list(finalCollection<A>ac){List<A>l=null;List<A>r=null;for(finalAa:ac){if(l==null){l=newList<A>(a,null);r=l;}else{l.tl=newList<A>(a,null);l=l.tl;}}if(r==null)return(List<A>)List.empty();elsel.tl=List.empty();returnr;}publicstatic<A>List<A>empty(){returnempty;}privateList(finalAhead,finalList<A>tail){this.hd=head;this.tl=tail;}publicAvalue(){if(this.hd==null)thrownewIllegalStateException("head has no value");returnthis.hd;}publicAgetValue(){if(this.hd==null)thrownewIllegalStateException("head has no value");returnthis.hd;}publicintlength(){intlen=0;List<A>l=this;while(l.hasValue()){len++;l=l.tail();}returnlen;}publicAhead(){if(this.hd==null)thrownewIllegalStateException("head has no value");returnthis.hd;}publicList<A>tail(){if(this.tl==null)thrownewIllegalStateException("has no tail");returnthis.tl;}publicbooleanisEmpty(){returnthis.hd==null;}publicbooleanisEmptyTail(){returnthis.tl.isEmpty();}publicbooleanhasValue(){returnthis.hd!=null;}publicMonoid<A>mempty(){returnList.empty();}publicMonoid<A>mappend(finalMonoid<A>a){if(isEmpty())returna;List<A>r=this;while(!r.isEmptyTail()){r=r.tl;}r.tl=(List<A>)a;returnthis;}public<B>Functor<B>fmap(finalFunction<A,B>f){if(isEmpty())returnList.empty();List<A>al=this;List<B>r=newList<B>(f.apply(al.value()),(List<B>)List.empty());List<B>r2=r;while(!al.isEmptyTail()){al=al.tail();r2.tl=newList<B>(f.apply(al.value()),r2.tl);r2=r2.tl;}returnr;}}
Now that we have Monoid let’s implement a Writer<W,A> monad. It’s used when we need to collect some values as we go, for example log messages. Note that W needs to be a valid Monoid, without this
we can’t collect values into one entity. Inside we use Tuple<A,W> to store values. We have tell method to mappend new Monoid values to Writer and by unwrapping the Tuple<A,W> we can
bind it to another Writer<W,B> monad.
publicclassWriter<WextendsMonoid,A>extendsAbstractMonad<A>{privateTuple<A,W>t;publicstatic<WextendsMonoid,A>Writer<W,A>writer(finalTuple<A,W>t){if(t==null)thrownewIllegalArgumentException("argument has no value");returnnewWriter<W,A>(t);}publicstatic<WextendsMonoid,A>Writer<W,A>writer(finalAa,finalWw){returnnewWriter<W,A>(Tuple.tuple(a,w));}privateWriter(Tuple<A,W>t){this.t=t;}publicTuple<A,W>runWriter(){returnthis.t;}publicWriter<W,Unit>tell(finalWw){returnnewWriter<W,Unit>(Tuple.tuple(Unit.unit(),(W)runWriter().second().mappend(w)));}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){finalWriter<W,B>m=(Writer<W,B>)f.apply(runWriter().first());returnnewWriter<W,B>(Tuple.tuple(m.runWriter().first(),(W)runWriter().second().mappend(m.runWriter().second())));}public<B>Monad<B>ret(finalBb){returnnewWriter<W,B>(Tuple.tuple(b,runWriter().second()));}public<B>Functor<B>fmap(finalFunction<A,B>f){returnnewWriter<W,B>(Tuple.tuple(f.apply(runWriter().first()),runWriter().second()));}}
Next let’s implement another monad called State<S,A>. Basicly StateMonad is needed when we need some mutable value across whole computation and in a sense it’s like programming in any imperative language.
State monad inside is actually a Function<S,Tuple<A,S>>. Basically we can imagine a State monad as a Function that takes some state S and returns Tuple that contains A and possibly changed state S. In a sense it’s implementation is like Writer and Reader monads combined. We have two methods get and set to get current state value and modify it during computation.
publicclassState<S,A>extendsAbstractMonad<A>{privateFunction<S,Tuple<A,S>>f;publicstatic<S,A>State<S,A>state(finalFunction<S,Tuple<A,S>>f){if(f==null)thrownewIllegalArgumentException("argument has no value");returnnewState<S,A>(f);}publicstatic<S,A>State<S,A>state(finalAa){if(a==null)thrownewIllegalArgumentException("argument has no value");returnnewState<S,A>(newFunction<S,Tuple<A,S>>(){publicTuple<A,S>apply(finalSs){returnTuple.tuple(a,s);}});}privateState(finalFunction<S,Tuple<A,S>>f){this.f=f;}publicFunction<S,Tuple<A,S>>runState(){returnthis.f;}publicState<S,S>get(){returnnewState<S,S>(newFunction<S,Tuple<S,S>>(){publicTuple<S,S>apply(finalSs){returnTuple.tuple(s,s);}});}publicState<S,Unit>put(finalSns){returnnewState<S,Unit>(newFunction<S,Tuple<Unit,S>>(){publicTuple<Unit,S>apply(finalSs){returnTuple.tuple(Unit.unit(),ns);}});}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){returnnewState<S,B>(newFunction<S,Tuple<B,S>>(){publicTuple<B,S>apply(finalSs){returnTuple.tuple(((State<S,B>)f.apply(runState().apply(s).first())).runState().apply(s).first(),s);}});}public<B>Monad<B>ret(finalBb){returnnewState<S,B>(newFunction<S,Tuple<B,S>>(){publicTuple<B,S>apply(finalSs){returnTuple.tuple(b,s);}});}public<B>Functor<B>fmap(finalFunction<A,B>f){returnnewState<S,B>(newFunction<S,Tuple<B,S>>(){publicTuple<B,S>apply(finalSs){returnTuple.tuple(f.apply(runState().apply(s).first()),s);}});}}
Now what if we need Reader monad and at the same time we need some mutation that State monad provides. Yes we need something that will combine the power of both monads into one.
This is what Monad Transformer can do. First of all any Monad Transformer is also a Monad. We can lift any Monad<A> into MonadTrans<A>.
Before we’ll start implementing Monad Transformers let’s write some abstract base class that every Monad Transformer will inherit.
It will have only one method called lift that will allow any Monad to be lifted into Monad Transformer.
First let’s implement MaybeT<M,A> monad transformer. Note that M needs to be a valid Monad and so we use extends type definition.
Internally MaybeT is a Monad<Maybe<A>>. We check it’s value by binding a function and inside we check if value is not empty we apply the provided function, if not we return wrapping it into
internal monad using ret method.
publicclassMaybeT<MextendsMonad,A>extendsAbstractMonadTrans<A>{privateMonad<Maybe<A>>m;publicstatic<MextendsMonad,A>MaybeT<M,A>maybeT(finalMaybe<A>a,finalMm){if(a==null)thrownewIllegalArgumentException("argument has no value");if(m==null)thrownewIllegalArgumentException("monad has no value");returnnewMaybeT<M,A>(m.ret(a));}publicstatic<MextendsMonad,A>MaybeT<M,A>maybeT(finalMonad<Maybe<A>>m){if(m==null)thrownewIllegalArgumentException("monad has no value");returnnewMaybeT<M,A>(m);}privateMaybeT(finalMonad<Maybe<A>>m){this.m=m;}publicMonad<Maybe<A>>runMaybeT(){returnthis.m;}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){returnnewMaybeT<M,B>(runMaybeT().bind(newFunction<Maybe<A>,Monad<Maybe<B>>>(){publicMonad<Maybe<B>>apply(finalMaybe<A>a){if(a.isNothing())returnrunMaybeT().ret((Maybe<B>)Maybe.nothing());else{return((MaybeT<M,B>)f.apply(a.value())).runMaybeT();}}}));}public<B>Monad<B>ret(finalBb){returnnewMaybeT<M,B>(runMaybeT().ret(Maybe.just(b)));}public<B>Functor<B>fmap(finalFunction<A,B>f){returnnewMaybeT<M,B>(runMaybeT().bind(newFunction<Maybe<A>,Monad<Maybe<B>>>(){publicMonad<Maybe<B>>apply(finalMaybe<A>a){returnrunMaybeT().ret((Maybe<B>)a.fmap(f));}}));}}
Next is EitherT<M,A,B> monad transformer. It’s written almost the same as MaybeT but inside it’s a Monad<Either<A,B>> but instead we operate with right and left values inside bind function.
publicclassEitherT<MextendsMonad,A,B>extendsAbstractMonadTrans<B>{privateMonad<Either<A,B>>m;publicstatic<MextendsMonad,A,B>EitherT<M,A,B>eitherT(finalEither<A,B>a,finalMm){if(a==null)thrownewIllegalArgumentException("argument has no value");if(m==null)thrownewIllegalArgumentException("monad has no value");returnnewEitherT<M,A,B>(m.ret(a));}publicstatic<MextendsMonad,A,B>EitherT<M,A,B>eitherT(finalMonad<Either<A,B>>m){if(m==null)thrownewIllegalArgumentException("monad has no value");returnnewEitherT<M,A,B>(m);}privateEitherT(finalMonad<Either<A,B>>m){this.m=m;}publicMonad<Either<A,B>>runEitherT(){returnthis.m;}public<C>Monad<C>bind(finalFunction<B,Monad<C>>f){returnnewEitherT(runEitherT().bind(newFunction<Either<A,B>,Monad<Either<A,C>>>(){publicMonad<Either<A,C>>apply(finalEither<A,B>a){if(a.isLeft())returnrunEitherT().ret((Either<A,C>)Either.left(a.left()));else{return((EitherT<M,A,C>)f.apply(a.right())).runEitherT();}}}));}public<C>Monad<C>ret(finalCc){returnnewEitherT(runEitherT().ret(Either.right(c)));}public<C>Functor<C>fmap(finalFunction<B,C>f){returnnewEitherT(runEitherT().bind(newFunction<Either<A,B>,Monad<Either<A,C>>>(){publicMonad<Either<A,C>>apply(finalEither<A,B>a){returnrunEitherT().ret((Either<A,C>)a.fmap(f));}}));}}
Now let’s implement ReaderT<E,M,A> monad transformer. Internally it’s implemented as Function<E,Monad<A>>. Basically it’s implementation mimics that of Reader monad however
instead of A value we are dealing with Monad<A>.
publicclassReaderT<E,MextendsMonad,A>extendsAbstractMonadTrans<A>{privateFunction<E,Monad<A>>f;publicstatic<E,MextendsMonad,A>ReaderT<E,M,A>readerT(finalFunction<E,Monad<A>>f){if(f==null)thrownewIllegalArgumentException("argument has no value");returnnewReaderT<E,M,A>(f);}privateReaderT(finalFunction<E,Monad<A>>f){this.f=f;}publicFunction<E,Monad<A>>runReaderT(){returnthis.f;}publicReaderT<E,M,E>ask(){returnnewReaderT<E,M,E>(newFunction<E,Monad<E>>(){publicMonad<E>apply(finalEe){returnrunReaderT().apply(e).ret(e);}});}public<B>Monad<B>bind(finalFunction<A,Monad<B>>f){returnnewReaderT<E,M,B>(newFunction<E,Monad<B>>(){publicMonad<B>apply(finalEe){returnrunReaderT().apply(e).bind(f);}});}public<B>Monad<B>ret(finalBb){returnnewReaderT<E,M,B>(newFunction<E,Monad<B>>(){publicMonad<B>apply(finalEe){returnrunReaderT().apply(e).ret(b);}});}public<B>Functor<B>fmap(finalFunction<A,B>f){returnnewReaderT<E,M,B>(newFunction<E,Monad<B>>(){publicMonad<B>apply(finalEe){returnrunReaderT().apply(e).bind(newFunction<A,Monad<B>>(){publicMonad<B>apply(finalAa){returnrunReaderT().apply(e).ret(f.apply(a));}});}});}}
Next monad transformer is WriterT<W,M,A>. This one is implemented internally as Monad<Tuple<A,W>> and follows the same pattern as MaybeT and EitherT monad transformer implementations.
Last monad transformer we are implementing is StateT<S,M,A>. It’s the most complex implementation among all monad transformers.
Internally it mimics State monad however it’s implemented as Function<S,Monad<Tuple<A,S>>> so general implementation
follows that of State with the difference that function returns monad but not a value. You can study this source code line by line
to better understand all the inner workings however I strongly encourage you to try implement it yourself. In a matter of fact try writing all the monad transformers from scratch yourself
and you’ll grok their beauty easily.
That’s all folks! We’ve implemented a small functional library in Java, it’s not complete and not as powerful as Functional Java, however doing so brings us a little bit closer to functional zen. Long road still lays ahead of us as we journey this path of functional programming, but we are stronger than we were! Good luck to you all adventurers and happy functional programming!