The road to monad-nature for OO washouts
There is a growing monad cottage industry engaged in popularizing the eponimous logical construct. With so much smoke, there has to be fuel, and indeed there is. Being a half-convert of the former monotheistic OO persuasion (now I serve a pantheon) I walk a thin line between functional orthodoxy and lewd heretical practices — for instance, I’ve been yet again mesmerized and misled by Scala while in pursuit of this monad thing. Here, I share my pain on the path to functional transcendence because it was an interesting battle. First, though, a simple note on why the suffering may be worthwhile.
Edsger W. Dijkstra said: “The required techniques of effective reasoning are pretty formal, but as long as programming is done by people that don’t master them, the software crisis will remain with us and will be considered an incurable disease. And you know what incurable diseases do: they invite the quacks and charlatans in, who in this case take the form of Software Engineering gurus.” Ouch! Let’s be humble and eat some crow at the altar of good, old, acerbic Edsger. For the literati who will point out flaws and sins: please be a teacher, rather than an inquisitor. Learning by burning at the stake not for a good experience makes.
First: why, oh why?
Why are monads A Good Thing worth all the effort they require? Philip Wadler says in “Monads for functional programming” (J. Jeuring and E. Meijer, editors, Advanced Functional Programming, Proceedings of the Baastad Spring School, May 1995, Springer Verlag Lecture Notes in Computer Science 925): “[Functionally] pure languages are easier to reason about and may benefit from lazy evaluation, while impure languages offer efficiency benefits and sometimes make possible a more compact mode of expression. Recent advances in theoretical computing science, notably in the areas of type theory and category theory, have suggested new approaches that may integrate the benefits of the pure and impure schools[, for instance] the use of monads to integrate impure effects into pure functional languages.”
Paraphrasing in more pedestrian terms: For a pure functional language the result of calling a function must depend only on the function called and its parameters; the result must not depend on anything external such as, say, changeable system or local state. This is limiting as it would require all state to be explicitly passed between functions, likely using function composition. A monad allows a shortcut. Simplistic example (inspired by and plagiarized from this): A part of an imperative (non-functional) program might look like this:
int x,y,z;
x = funct1(1,2);
y = funct2(x);
z = funct3(x,y,5);
x = funct4(y);where x,y and z are variables. In a purely functional program, however, state is immutable (e.g. it is illegal to reassign to x) and everything should instead happen by functional composition:
funct3(funct1(1,2),funct2(funct1(1,2)),5)Not exactly readable, and func(1,2) needs be called twice. A monad allows a better manner to circumvent the problem.
“Dude, I’m all for being impure!” Yes, understood. But there are circumstances in which monads make for happier customers even among impure software engineers. The advantage can be of universal value in providing additional useful structure, even if impurity is tolerated or even welcome.
OO washouts unfortunately run into a brick wall and a steep learning curve when confronted with monads. That’s because OO minds are used to decomposing coding problems in terms of mutable state, and the associated behavior needed to mutate it, whereas functional minds are used to decomposing coding problems in terms of polymorphic behavior, and associated types of immutable state. Monads are tools for functional decomposition of coding problems, and are articulated in terms of polymorphic behavior (in a functional sense), changeable types, and (mostly) immutable state. This is a huge mismatch, and there are a lot of sharp curves that must be negotiated before experiencing functional nirvana. If weaned on strict OO religion it’s hard to realize there is a paradigm shift bigger than moving from assembly to OO. Scala, being hybrid, masks this shift and allows an easier learning curve, at a price. For instance, Scala may be likely to encourage a functional newcomer with the false impression that all collections are monads and vice versa. That’s a slippery banana peel on the way to functional thinking.
The road to monad-nature goes through a narrow bridge where it is necessary to change the nature of the question being asked. Old OO question: “How do I model and break up this problem domain into an elegant solution domain having pieces with encapsulated mutable state and some associated behavior for mutability?” New Functional question: “How do I model and break up this problem domain into an elegant solution domain having pieces with (mostly) immutable state and some associated polymorphic (in a functional sense, i.e. not involving inheritance) behavior?”
So a monad is defined in terms of behavior and types, not in terms of state and how to change it. Huge difference. It happens that parts of math are defined in the same way as monads, except in terms of transformations from some domain to some codomain (same-o, same-o). In particular, monads are the spawn of Category Theory. That’s largely irrelevant, in practice, as long as we keep an eye on the behavior, the types, and the constraints associated with the same. Math-wise life can become interesting, because a behavior becomes a theorem, and then you have to prove it — usually in a very general and abstract environment full of greek letters. It’s hairy, because in proving theorems there is more honor when the reasoning is on abstractions of abstractions. That’s usually good for generality, but bad for intuition. Of course, mathematicians like to prove the general case, and then give a specialization from the top down as a particular circumstance; still bad for intuition, if the top is oh, so beautifully abstract!
A way out of the “what?” stupor is to try a new start from the results, walking backwards from the bottom: something like confirming a specialization, say, from a practical example. One can argue that works only for that one particular example, proves nothing, and the approach lacks honor. That’s OK, it’s only a start. For those who prefer to start with a smudge of grease on the forehead (abstractions will be welcome later, after intuition has kicked in), let’s dig in and try to turn that light bulb on. When intuition is in place, then maybe the rest of the picture will start making more sense.
A few Scala constructs need some level of understanding prior to dealing with monad-nature. Think of this as a video game, where you need to go through boring levels before you get to chase Princess’s tails.
Type Constructors
From the perspective of a Java redux, and for most of us with backgrounds in traditional statically typed languages (yes, the compiler is my best friend, I’m a true believer), the type system of Scala is a different animal (see for instance “Generics of a higher kind”). Scala supports, among the rest, type level programming and type constructors.
A type constructor in Scala looks like T[ _ ]. A type constructor acts like a constructors, but at the type level, e.g. a type constructor creates a new type, rather than a new instance of an object. Type constructors are ( * -> * ) functions, i.e. ‘takes one type, returns another type’ functions. For instance List[ _ ] is a type constructor like (* -(+)-> *) where (+) shows the variance bound of List in Scala, which is in fact List[+A] for an immutable List. Tuple2[ _,_ ], or Map[ _._ ] have type (( * -> * ) -> * ) where, given two types, another type is returned. And so on.
“Dude, you’re describing generics!” Hmm, not really. In Java (as an example for generics), List<T> is a first-order type abstraction: you can use it once only; perhaps crudely, in other terms, it’s not a “type variable,” but rather it is a “type placeholder.” In C maybe (ah! I’m going to be lynched for this) you could have used a macro substitution. The previous sentence intends to represent that after you replace a macro, the macro has been replaced—and that’s the end of it: you can use macros as a one-stage trick only, no further application is possible. First-order generics are like “one-stage type macros” in that respect. This metaphor does not imply any other similarity between C macros and Java generics! I agree ahead of time it’s a poor metaphor and should not be extended beyond its very limited scope and intent. On the other hand, in Scala, because of type level programming, List[ _ ] is a construct(or) of greater complexity. For instance: If you have dealt with Scala long enough to wonder about monads, you’ve run for sure into partially applied functions. In the same way a function that takes more than one argument can be written as a partially applied function, a type constructor that takes more than one type can also be partially applied. This gives rise to the “type lambda” Scala idiom, representing an anonymous function at the type programming level. Example:
type TypeCarrier[M[_]] = M[Int]
val t2 : TypeCarrier[({ type L[A] = Tuple2[String, A] })#L] = ("A",2)Here, TypeCarrier is a type member (crudely, a real “type variable”), initialized with a type constructor that takes an Int; note that M[ _ ] can be any type constructor… t2 is a Tuple2 of type [String,Int]. The expression to the right of : is a “type lambda” idiom, which says roughly to use the type constructor Tuple2[String,A] using for A the type parameter already available from TypeCarrier. QED.
The Mighty Monad
A monad begins as an augmentation to a type constructor. This is a way to write a monad (there is more than one expression of the monad-nature):
trait MonadCommon[TYPE_LIFT[_]] {
def iden[DOMAIN](m: TYPE_LIFT[DOMAIN]): TYPE_LIFT[DOMAIN] = m
def unit[DOMAIN](eta: DOMAIN): TYPE_LIFT[DOMAIN]
}trait MonadB[TYPE_LIFT[_]] extends MonadCommon[TYPE_LIFT] {
def bind[DOMAIN, CODOMAIN](typeDomain: TYPE_LIFT[DOMAIN])
(bindFun: (DOMAIN) => TYPE_LIFT[CODOMAIN]): TYPE_LIFT[CODOMAIN]
}
iden is a trivially simple, and optional, identity function. It’s useful under certain cases in modeling the constraints that monads must live by. unit is the, hmm, constructor. If you have an item eta from the domain, unit is what adds to that item the additional behavior necessary to turn eta into the type that this monad augments. Caution: at this point, it’s good to remember we are in a functional paradigm. The monad augments the type constructor, but it’s meaningless to think that the monad is-a object of that type. Children are an OO concept, and are not part of the functional bag of tricks; that’s the reason for humming when calling unit the, hmm, constructor. For example: If our friend Eta steps into her car to go to the grocery store, Eta-in-the-car is an augmentation of the car (and, I would say, an augmentation of Eta, too), but most of us will agree that “the car is-a Eta” is a meaningless statement. However, Eta-in-the-car is a construct with monad-nature that, for some particular purpose, has identity and features of its own that are more useful than any car alone or our friend Eta alone.
bind is an interesting and very abstract piece of equipment. When provided with an item matching the type signature of the type constructor, it will associate with this item a derived-item, of a type related to item via the type constructor. The derived-item is obtained from item using a function (to be provided) that transforms the domain of item into the derived-item.
“What a pile of nonsense!” Agreed, it’s too abstract to make sense yet! This is like describing your trip from Boston to Chicago stating that you are, hmm, constructed by unit(you) into a you-that-can-travel-from-Boston. bind endows you with some kind of magic (in the form of a specific bindFunc) that, when applied to you-in-Boston, can transform that entity into a you-in-Chicago entity. However, bind at this time is completely oblivious if you’ll be flying, driving or riding a bicycle, or routing via Buffalo or Cleveland. All that bind states at this point is that bind(you-in-Boston)(bindFunc) will produce you-in-Chicago. How you get there is an implementation detail captured in bindFunc alone. Note that bind(you-in-Boston) is a partially applied function for which bindFunc still needs to be defined.
“Dude, but how I get there really matters!” Alas, agreed. That’s part of the difference between mathematicians (of Category Theory fame) and engineers (of “recursion could overflow my stack” fame). Still the, hmm, travel monad (rather, a specialized example of monad-nature) allows you to state something like “Just assume you can get from Boston to Chicago.” At that point, trusting the assumption, your concern is not any longer about getting to Chicago, but simply what to do after you are there. Also, note the obvious: bindFunc is a function, not an object, for those among us that are maybe thinking in term of a Delegate or a Strategy pattern: not the same thing! Also, if you think in terms of Boston or Chicago as a piece of changeable state now associated with you, do please note that nowhere in MonadB there is any hint of mutability whatsoever. The difference is in the polymorphic type. It really, really is neither a Delegate nor a Strategy. We’re not in Kansas any more, Toto.
bind is called bind because it associates you-in-Boston with the magic (as in bindFunc) that whisks you away to Chicago. Warning: don’t carry this ‘travel’ metaphor any further. Monads are positively not travel agents; that’s only a particular specialization of the monad-nature. Another specialization example: bind(you) may still be applicable to you-in-Boston, but if bindFunc is something totally different, then maybe bind(you-in-Boston)(bindFunc) instead of whisking you to Chicago on a magic carpet will instead stuff you with cream puffs and assorted pastries, producing you-in-Boston-with-Indigestion. That’s where behavioral abstraction and functional polymorphism apply. bind(you-in-Boston) is a partially applied function. The (arbitrary) outcome is still captured in the type that bindFunc yields, except in this different specialization of monad-nature the change it represents is not one of geographical location, but one of gluttony and intestinal discomfort. Note that the eventual type of the transformation is indeed arbitrary, to the extent that bindFunc and its return type are arbitrary. We also agree that monads are positively not pastry chefs either, yes?
“Whoa! I can do anything I want with a monad then.” Within some limits. There are three monad laws that shall be obeyed, or else. Here they are (inspired by this):
trait MonadBLaws[DOMAIN, CODOMAIN, TYPE_LIFT[_]] extends
MonadLawAsserter[DOMAIN,CODOMAIN,TYPE_LIFT] {
this: MonadB[TYPE_LIFT] => def leftIdentityLaw(d: DOMAIN, bindFun: (DOMAIN) => TYPE_LIFT[CODOMAIN]) = {
val aut1 = bind(unit(d))(bindFun)
val aut2 = bindFun(d)
isTLEqual(aut1, aut2)
} def rightIdentityLaw(tl: TYPE_LIFT[DOMAIN]) = {
val aut1 = bind(tl)(unit)
val aut2 = tl
isTLEqual(aut1, tl)
} def associativeLaw(tld: TYPE_LIFT[DOMAIN],
bindFunDC: (DOMAIN) => TYPE_LIFT[CODOMAIN],
bindFunCZ: (CODOMAIN) => TYPE_LIFT[Z]) = {
val aut1 = bind(tld)(d => bind(bindFunDC(d))(bindFunCZ))
val aut2 = bind(bind(tld)(bindFunDC))(bindFunCZ)
isTLEqual(aut1, aut2)
}
}
The left identity law states that if we take a domain value, construct it with unit, and then associate some behavior to it using bind and bindFunc, the result must be the same as applying bindFunc directly to the domain value. In other words, the domain value still needs be available so that we can apply bindFunc to it, even when it is augmented into a monad. In different terms: a monad must ‘remember’ the domain value, so that it can use it.
The right identity law states that if bindFunc is unit, then bind must be equivalent to a NOP. This is because in such case all that bind does is to take the domain value and rebuild it into the type constructor using unit. In other words, bind will unshell the value, and then unit will put it back into the same shell. The overall result is to warm up the CPU.
The associative law states that in a chain of applications of bind, it does not matter how the applications are nested, meaning, it does not matter which ordered pair of operands is processed first. (Note this does not imply the need to be commutative, even if it does not hurt.) It can be argued that the order of operations is important when there are side-effects, and that monads are at times useful precisely to encapsulate side effects. Why should associativity hold, thereby constraining the applicability of monads in that case? Because a monad is a monad is a monad, and monad-nature may apply to the encapsulation of side effects, but monad-nature is not the arbitrary encapsulation of side effects.
This inconvenient aspect of the monad-nature can be, however, a conundrum. Let’s investigate it. Monad operations (such as bind) are a distinct layer of operations, as they belong to the “augmented” type constructor: Eta-in-the-car can travel to places where Eta alone (presumably on foot) could not go, for instance on a 70-mile ride to town, and through the town’s drive-through car wash, and on to pick up her cleanliness freak date (who lives in town) for an evening to the drive-in theater. The associativity requirement demands to build these operations as any composition of orderer pairs. As long as the outcome is built from the same operations (with ordered operands), the outcome must be the same. Say you’re making a cake: mix batter, bake, eat. The outcome is a full tummy. You can mix the batter, and go to the gym. Later, you bake the cake and eat it. Or you can mix the batter, and put the cake in the oven. While it cooks, you go to the gym. Then you come home and eat it. Same-o. Extend this latter example by thinking that even if each stage produces a different value, the end result is the same. So monads can work to encapsulate side effects when the side effects are associative, too, and respect the associativity requirement of the monad-nature. In the bigger picture, there must be some order introduced into the chaos of side effects to reduce the original chaos to a lesser chaos.
By the way: This piece of code is missing from above:
trait MonadLawAsserter[DOMAIN,CODOMAIN,TYPE_LIFT[_]] { type Z def isTLEqual[TLLHS <: TYPE_LIFT[_], TLRHS <: TYPE_LIFT[_]]
(lhs: TLLHS, rhs: TLRHS)
(implicit evidence: TLLHS =:= TLRHS): Boolean = { lhs.equals(rhs)}
}
The (implicit evidence: TLLHS =:= TLRHS) part means that the Scala compiler (at type level programming) should enforce that the types represented by TLLHS or TLRHS must be the same type. In turn, TLLHS or TLRHS are declared as subtypes of TYPE_LIFT. I could have saved some typing and used only one of them at this time, but maybe in the future I’ll add type variance, so be it. (More details).
Another Way
There is another way to write a monad more in line with Category Theory, which declares a monad to be a construct comprising a functor and two natural transformation altogether abiding by certain laws as a whole. Again, monad-nature can be expressed using different constructs. (For the curious: yes, there are even more.)
One of the two natural transformations we have already met. It’s the, hmm, constructor already called unit. But what is a natural transformation? Or a functor?
Natural Transformation
This is a technical term borrowed (factoid) from Category Theory, which here is bastardized to mean a polymorphic function. Here is boilerplate for a natural transformation in Scala:
trait NaturalTransformation[TYPE_LIFT_F[_], TYPE_LIFT_G[_]] {
// takes a type constructor, returns another type constructor
def transform[DOMAIN](fa: TYPE_LIFT_F[DOMAIN]): TYPE_LIFT_G[DOMAIN]
}The interesting part of a general purpose natural transformation is that the incoming and outgoing type constructors operate on the same domain; the transformation has some constraints attached, by virtue of being ‘natural,’ when considered in association with Functors.
Functors
A functor is a technical term borrowed (factoid) from Category Theory, which, when expressed with Scala, means as usual something more specialized than its theoretical definition. This is a functor in Scala:
trait CovariantFunctor[TYPE_LIFT[_]] {
def map[DOMAIN,CODOMAIN](ftc: TYPE_LIFT[DOMAIN])
(mapFunction: DOMAIN => CODOMAIN): TYPE_LIFT[CODOMAIN]
}A functor is yet another augmentation to a type constructor TYPE_LIFT[ _ ]. A functor uses a function to map a type constructor to another type constructor; let’s call this function ‘map’. This ‘map’ function must be implemented on the domain of the type constructor that the functor will extend. The interesting part of ‘map’ is that the incoming and outgoing type constructors are the same, but operate, in general, on different domains, as transformed by ‘map’ which, in turn, has a structure-preserving requirement. The structure-preserving requirement is spelled out, among the rest, by the functor laws: identity, and composition (not the same as the monad laws, more on this in a future post). These require that ‘map’ may alter only the elements (but not the ‘structure’ itself) contained in the ‘structure’. Each elements is modified individually by mapFun; collectively, the ‘shape’ of the ‘structure’ (for instance, the length of a collection) is not changed when ‘map’ is applied (as in, it must not change). Whence the structure-preserving property.
A functor is covariant if f compose g is the same as F(f) compose F(g); full disclosure: there is a contravariant Functor where the composition law requires that f compose g be the same as F(g) compose F(f). Note: being used to Scala, which also has a ubiquitous homonymous function, one may wonder why it is that ‘map’ here is a partially applied function that takes a type constructor (in our case ‘ftc’) as one of its arguments. This is because, in a functional world, functions are self-standing functions, as opposed to OO ‘class methods’ that likely have some state attached by virtue of belonging to some class. Whereas a ‘class method’ probably has an already available workalike for ‘ftc’, a standalone function needs have one provided, whence the ftc parameter.
Functors vs. Natural Transformation
In general, a functor has the same type constructor on different domains; a natural transformation will have different type constructors on the same domain.
Another expression of monad-nature
Here we go:
trait MonadJM[TYPE_LIFT[_]] extends MonadCommon[TYPE_LIFT] with CovariantFunctor[TYPE_LIFT] { def join[DOMAIN](mu: TYPE_LIFT[TYPE_LIFT[DOMAIN]]): TYPE_LIFT[DOMAIN]
}
join is the other natural transformation mentioned early, which, with map, builds a construct (MonadJM) equivalent to the first one with bind (namely, MonadB) that we have already discussed. Since the two constructs are equivalent, they can be coded in terms of each other like so:
trait MonadJMToMonadB[TYPE_LIFT[_]] extends MonadB[TYPE_LIFT] {
this: MonadJM[TYPE_LIFT] => override def bind[DOMAIN, CODOMAIN]
(typeDomain: TYPE_LIFT[DOMAIN])
(bindFun: (DOMAIN) => TYPE_LIFT[CODOMAIN]): TYPE_LIFT[CODOMAIN] = {
join(map(typeDomain)(bindFun))
}
}trait MonadBToMonadJM[TYPE_LIFT[_]] extends MonadJM[TYPE_LIFT] {
this: MonadB[TYPE_LIFT] => override def map[DOMAIN, CODOMAIN]
(typeDomain: TYPE_LIFT[DOMAIN])
(mapFun: DOMAIN => CODOMAIN): TYPE_LIFT[CODOMAIN] ={
bind(typeDomain)(mm => unit(mapFun(mm)) )
} override def join[DOMAIN](mu: TYPE_LIFT[TYPE_LIFT[DOMAIN]]): TYPE_LIFT[DOMAIN] = {
bind(mu)(iden)
}
}
Since MonadJM can be made to look like a MonadB, then it can be tested with the same monad laws used for MonadB. Let’s do just that. First, however, we need to create some real instances of monads. That’s not too difficult or abstract if we use a Scala Sequence (that’s convenient, insightful and quick, but not all monads are collections):
class SeqMonadBExample[X](s: Seq[X]) extends MonadB[Seq]{
override def unit[X](x: X): Seq[X] = Seq[X](x)
override def bind[X, Y](xs: Seq[X] = s)(f: (X) => Seq[Y]): Seq[Y] = xs.flatMap(f)
}class SeqMonadJMExample[X](s: Seq[X]) extends MonadJM[Seq] {
override def map[X, Y] (sx: Seq[X] = s) (f: X => Y): Seq[Y] = sx.map (f)
override def unit[X](x: X): Seq[X] = Seq[X](x)
override def join[X](ssx: Seq[Seq[X]]): Seq[X] = ssx.flatten
}
all the naming is mapped to the Scala monikers: bind is flatMap, join is flatten, map is map. The following is an assertable implementation of MonadB or MonadJM:
class SeqMonadBExampleBLaw[D,C,T[_],X](s: Seq[D])
extends SeqMonadBExample[D](s) with MonadBLaws[D,C,Seq] {
type Z = X
}class SeqMonadJMExampleBLaw[D,C,T[_],X](s: Seq[D])
extends SeqMonadJMExample[D](s) with MonadJMToMonadB[Seq] with MonadBLaws[D,C,Seq] {
type Z = X
}
And this is the test:
class MonadicBTest extends FunSuite with BeforeAndAfter with BeforeAndAfterAll with LazyLogging { val bindFunSsI : (String) => Seq[Int] = (s: String) => s.split(" ").map(w => w.length)
val bindFunIsB : (Int) => Seq[Boolean] = (i: Int) => Seq(0==i%2)
val s = "the little brown fox jumps over the lazy dog"
val sAsSeq = Seq("the","little","brown","fox","jumps","over","the","lazy","dog")
val smbel = new SeqMonadBExampleBLaw[String,Int,Seq,Boolean](sAsSeq)
val smjmel = new SeqMonadJMExampleBLaw[String,Int,Seq,Boolean](sAsSeq) test("leftIdentityLaw") {
assert(smbel.leftIdentityLaw(s,bindFunSsI))
assert(smjmel.leftIdentityLaw(s,bindFunSsI))
} test("rightIdentityLaw") {
assert(smbel.rightIdentityLaw(sAsSeq))
assert(smjmel.rightIdentityLaw(sAsSeq))
} test("associativeLaw") {
assert(smbel.associativeLaw(sAsSeq,bindFunSsI,bindFunIsB))
assert(smjmel.associativeLaw(sAsSeq,bindFunSsI,bindFunIsB))
}
}
To code your own monads, it’s necessary to code unit and bind, or unit, map and join. And equals, if needed, for testing. And pass the law test. If your specialization of monad-nature encompasses side effects, then the scope of equals needs include the side effects, or some surrogate. An example is available with the second installment in this series.
Disclaimer
The code above is intended to develop intuition, rather than as a production grade handiwork. If you are looking for a ready-to-use monad implementation in Scala, try ScalaZ
Credits
This post rehashes a lot of existing material created by others in an attempt to provide a different perspective on connecting the dots. I am indebted to all sources linked inline for insight and examples, some of which have been lifted with little or no changes: plagiarism is the greatest form of praise. No credit is claimed for work of others that has been represented in this post, to whom full attribution is granted, with a thank you! for your help. If I have forgotten to cite a source, let me know and correction will be applied. Any transcription mistakes are mine. If something has been lost in translation, the fault is mine, too. Other great sources of inspiration for this post:
Functional Programming in Scala, by P Chiusano, R. Bjarnason, Manning publications
http://blogs.atlassian.com/2013/09/scala-types-of-a-higher-kind/
http://james-iry.blogspot.com/2007/09/monads-are-elephants-part-1.html
