# Monads (with snippets in R and Swift)

The literature and information around monads and categories is sometimes confusing because it has many aspects and depending on the background many overlapping or equivalent terms are used. Haskell uses the term ‘monad’ probably as it should (i.e. close to the algebraic theory) while F# talks of workflows and computational expressions. In a category context monads are explained with references to endo-functors while if you talk about programming you will see references to bind/return methods. I want to present my take on the matter and hope it helps someone.

Why does it show up all over the place in recent years? Simply because programming is now as much about functions and functionals as it is about (data) structures. Languages like R and JavaScript deal with functions in the same way as they deal with other data types. As soon as you deal with combining functions you end up in situations where monads describe on a high level what is going on. Very simple, if you have two functions $f: A\mapsto B, g: A \mapsto B$ how do you compose them? Clearly $f(g(a)), \; a\in A$ makes no sense, so how to handle this? The question how to compose functions leads to monads.

What languages support monads? It depends how you define support here. Pretty much every programming language can implement the monadic definition but few leverage it. Probably only Haskell and F# have a deep articulation and go beyond the couple of methods you need to have a monad. The term ‘workflow’ used in F# context is actually appropriate since indeed most languages do not enable workflows and the benefits of side-effects. What do we mean by side-effects? It means that you can write code which does more than what it looks like. For example, a true monad/workflow implementation allows one to write something as simple as

workflow(
x <- 5/0
return x
)


while the underlying monad/workflow takes care of exception handling, sending an Email to your boss, loggin the error and whatnot. This is what people mean when referring to side-effects. This kind of support is native in F# and Haskell but it would be a challenge in, say, Ruby or JavaScript. Obviously, any language can do all of the side-effects but it’s not baked into a reusable bit which can be applied by simply wrapping existing code in a monad block. It’s language extensibility in a way.

Where does the babylonian confusion come from? Categories and monads are part of algebra and from a purely mathematical point of view defined via the concept of a functor. As such, there is never a reference to programming concepts like ‘function’ and data type. Examples of monads go far beyond the world of programming and code. In fact, the richness of the theory is precisely that it can talk about biological patterns, cooking recipes and code constructs in the same way. Now, when applied to coding you inevitable deal with data types and methods (functions) and in those terms the concept of monad is in a way redefined in terms of ‘bind’ and ‘return’ methods. So, a monad is much more than a class with a bind and a return/unit method but if you neglect the general framework you only see those concepts. I think that’s the reason why there is a gap between the programming and the algebraic world.

I will try to highlight with some Swift code how one goes from a well-known situation to monads. Well, not a full-fledge monad implementation like F#. Let’s call it a ‘light’ version of monads.

Imagine you have the following protocol

protocol Monoid {
typealias ItemType
var unit: ItemType { get }
func compose(left left: ItemType, right: ItemType) -> ItemType
}


The term monoid has a precise mathematical meaning but you can think of it as just a protocol (interface definition in other languages). It defines something which is composable.
A concrete implementation of this protocol is easy enough. In particular, you can invent something like this

struct MonoidOfFunction: Monoid {
let unit: T -> T = { $0 } func compose(left f: T -> T, right g: T -> T) -> T -> T { return { g(f($0)) }
}
}


This works because the generic type T is both the domain and the target of the functions. Now, try this when they are not the same, say $f: T \rightarrow S$. We get into the situation I described above; you can compose them unless you have some glue with signature

$S \rightarrow (T \rightarrow S) \rightarrow S$

This is called the bind-method. The unit function is usually called the return-method. Obviously, if you have a bind method you can have a composition. Let’s elaborate a bit and write it out;

class  Box {
var value:Int
init(v:Int){
self.value = v
}
}

typealias BaseType
func compose( f: Map, g: Map) -> Map

}
func unit (b:Int)->Box{
return Box(v:b)
}
typealias Map = Int-> Box
func compose( f: Map, g: Map) -> Map
{
return {self.bind( f(\$0), f: g)}
}

func bind( m:Box, f:Map)-> Box {
return f(m.value)
}

}


The Monad protocol is usually what you see in other software-related articles and expositions as the definition of monad. Again, this is indeed the case if you narrow category theory down to coding. I will refrain from explaining how the endo-functor definition maps to this one. I guess it would confuse most people.
Now, can one do in Swift what comes out of the box in F# and Haskell? Partially. Probably it is possible with a lot of work. In fact, typical scripting languages like JavaScript and R have an advantage here because parsing and evaluation of strings as code is what makes it possible. In strongly typed languages things are more rigid and one would have to manipulate the AST (abstract syntax tree) at some point.

Anyway, if you would wish to have something like a workflow in Swift you would go like this

infix operator  <- { associativity left precedence 140 } // 1
func <- (inout left: Int, right: Int) -> Box{ // 2
left = right
return Box(v: left)
}
var b:Int

func release ( right: Int)-> Box {
return Box(v:right)
}
var k:Int = 0;
var code:[Box] = [k <- 4, k <- 7, release(k)]


which is easy enough with simple infix operators but needs deep parsing if you want to include all language constructs in the code array.

If you want to do something similar in R you can do it succinctly like so

 Box<- function(x){
list(value=x)
}

"%<-%" <- function(x,y) call("<-",substitute(x),substitute(y))
release <- function(x) call("return",substitute(x))

pars<-function(...){
lines = list(...)
for(k in 1:length(lines)){
line= (lines[[k]])
if(line[[1]]=="<-") {
assign(paste(line[[2]]), Box(line[[3]]), envir = parent.frame())
}
else {
return(eval(parse(text = paste(line[[2]]))))

}
}
}

pars( x%<-%5, y%<-%6, release (x))


A talented guy took it further and even switched on some R-magic I was unaware of. Take a look at this:

# custom infix for inside the workflow
# to differentiate with the same constructs outside the workflow

"%<-%" <- function(x,y) call("<-",substitute(x),substitute(y))
returm <- function(x) call("return",substitute(x))
exec <- quote

join <- function(ss,sep) {
res <- ""
for (s in ss) {
res <- paste(res,s,sep=sep)
}
res
}

list2call <- function(calls) {
t <- call("{")
for (x in calls) t[[length(t)+1]] <- x
return(t)
}

newfunc <- function(a,b) {
f <- eval(parse(text=paste("function(",a,"){}",sep="")))
body(f) <- if (is.list(b)) list2call(b) else b
return(f)
}

function(...) {
ss <- list(...)
f <- (function(i,a,b) { if (i>length(ss)) return(newfunc(a,b))
s <- ss[[i]]
if (s[[1]] == "<-") {
r <- Recall(i+1,s[[2]],list())
newfunc(a,append(b,call("bind",s[[3]],r)))
} else if (s[[1]] == "return") {
Recall(i+1,a,append(b,call("ret",s[[2]])))
}
})(1,"",list())

params <- append(as.list(parent.frame()),list(bind=bind,ret=ret))
f <- evalq(eval(parse(text=join(deparse(f),""))),params)
f()
}
}

# the inevitable Maybe monad of course
bind = function(x,f) if(is.na(x)) NA else f(x),
ret = function(x) x
)

maybe_test <- function() {

loves_list <- list(
c("Taro","Miki"),
c("Jiro","Hanako"),
c("Saburo","Hanako"),
c("Daisuke","Youko"),
c("Shunsuke","AnyGirl"),
c("Masatoshi","AnyGirl"),
c("Miki","Taro"),
c("Hanako","Daisuke"),
c("AnyGirl","Masao")
)

lover <- function(x) {
for (p in loves_list) {
if (x == p[1]) return(p[2])
}
return(NA)
}

do <- maybe_do

couple_test <- function(a,b,lover) do (
x %<-% lover(a),
y %<-% lover(x),
returm(x == b && y == a)
)

rival_test <- function(a,b,lover) do (
x %<-% lover(a),
y %<-% lover(b),
returm(x == y)
)

jealousy_test <- function(a,b,lover) do (
x %<-% lover(a),
y %<-% lover(x),
returm(y != a && y == b)
)

run <- function(test,a,b) { print(paste(substitute(test),a,"-->",b,":",test(a,b,lover)))
}

run(couple_test,"Taro","Miki")
run(couple_test,"Jiro","Miki")
run(couple_test,"Daisuke","Youko")
run(rival_test,"Taro","Jiro")
run(rival_test,"Jiro","Saburo")
run(jealousy_test,"Shunsuke","Masao")
run(jealousy_test,"Shunsuke","Taro")
run(jealousy_test,"Jiro","Saburo")
}

maybe_test()


If you want to have an very understandable and applied intro to category theory I can highly advice “Category theory for the sciences” by Spivak. It will boost your thinking to the next level.

You can also read about how category unifies many fields in “A kaleidoscope from F# and monads”. Finally, some people have extensive blogs about the category universe, check out Bartosz Milewski’s Programming Cafe for instance.

Tags: