Monads

Introduction

Before writing an article on monads I would like to say that the subject seems to be a bit less controversial these days then it was a few years ago. Functional Programming has been entering mainstream programming for years now and even the most hardened Object Oriented programmers have heard terms and phrases from the FP paradigm, like:

• Recursion
• Functions
• Functors
• map

and of course, this article’s subject:

Monads…..

Because of this shift to a more functional approach I would like to do a more theoretical version of the monad what most people are doing. This article is more like a recipe for creating monads than a mathematical definition. We are however going to circle back to monoids and Category Theory at the end of the article.

You might think: “Why not give a definition of manods and be done with it?”. This is because compared to the current mainstream way of programming monads fall into something other than a pattern. Yes, we can create monads through our normal code; but, monads can only be recognised through knowledge instead of pattern. In this document you will notice that I do not take a direct approach to defining monads, I will describe what it is to be monadic and from that description we will dive into a couple of examples of monads. After these examples we might circle round and say what a monad is.

I am going to provide examples in C#, F# and JavaScript. I am going to ignore Haskell, Lisp and Lispy languages like Clojure because I don’t think that adding these languages provides any more relevant information on monads. I do think that learning Haskell is almost the only way to learn functional programming because the resources out there for learning Haskell are amazing and Haskell is the purest functional language out there. I also believe that Lisp is a superb language and everyone should learn it! What it boils down to is that I really think that learning a programming language a year is a great way to become a master programmer; but, learning monads is quintessential to mastering business applications and that is what this article focuses on.

This tutorial will start with simple objects representing monads, we will add functions to these objects so that we flesh out the functionality. At the end of the article we will walk backwards and look at monoids followed by a look at how we can come back to monads from them.

Disclaimer: I’m a JavaScript programmer. This might not mean anything to you, but it means a lot to me. I circumvent all pretense of a type system. I think type systems often serve an academic purpose. Our applications are usually not so difficult as to warrant the use of a compiler or a strong type system. Anyone who tries to sell the profession of writing Line of Business Applications as being difficult should look at Image Processing, Data Mining, Data Transformations and the necessary performance optimizations needed there. We, as a profession, tend to be lazy in general. I’ve met a lot of C# programmers who simply do not care about learning other programming languages or monads. I’ve also met Functional Program enthusiasts who do not want to learn the OOP paradigm. I think that monads are worth your while to learn just as I think OOP is worth every FP’s effort.

What do you need to know to read this article?

• C# at an intermediate level
• JavaScript at a intermediate level
• F# at a beginner level

One of the most important concepts you need to know in C# is generics. You should also be aware of what a class is and how you can use them. From a JavaScript point of view you’ll have to be familiar with prototypes and object literals, I can advice reading JavaScript the good parts a couple of times.

F# is a different story. I do expect the reader to be familiar with the F# syntax. Getting to a point where you might be familiar with F# takes a long time, so I think it might be the most difficult thing to ask of the reader. If you are not familiar with F# you can still give this article a try but you are sure to miss subtle nuances.

The last thing I want to say about the following code is that the examples are always the hardest part of writing a substantial article on programming. Please don’t judge me too harshly for my flimsy examples.

Constructors

What is a constructor? A constructor is a function which sets up the initialization of an object. In C# a constructor would look something like:

class Person {
    public Person() {
    }
}

When we look at this notation I always get a bit “itchy”. The fact that there is something which looks like a function but returns nothing scares me. In ES6 this looks a bit different:

class Person {
    constructor() {
    }
}

For some reason, this JavaScript code seems less strange to me; because you write the actual word constructor instead of using the name of the class, you get the feeling that this function is special. Apart from this fact, JavaScript does not specify return types so compared to other functions there is nothing different from the constructor.

Sometimes, in C#, you see the following pattern:

public class Person {
	public readonly string Name;
	private Person(string name) {
		this.Name = name;
	}

	public static Person CreatePerson(int id) {
		return new Person("Peter Pan");
	}
}

This pattern revolves around the factory pattern but it is a really special case. Here the factory and the concrete implementations are in the same class. I don’t particularly like this pattern, I feel that construction of a object should be done through a constructor or else through a factory, never through a hybrid. Here we might have opted for the option:

public interface IPerson {
	string Name { get; }
}
interface IPersonFactory {
	IPerson CreatePerson(string name);
}

public class Person : IPerson {
	private readonly string _Name;
	public string Name { get { return this._Name; }}
	public Person(string name) {
		this._Name = name;
	}
}

public class PersonFactory : IPersonFactory {
	public IPerson CreatePerson(string name) {
		return (IPerson)new Person(name);
	}
}

In F# we’d use a record and a simple function to get the job done:

type Person = { name : string }
let createPerson = { name = name }

let peterPan = createPerson "Peter Pan"
printf "%A" peterPan

If you really, really want the function signature to be lifted out of the declaration you could write:

// define the type
type CreatePerson = string -> Person

// implement the concrete function
let createPerson:CreatePerson = fun name -> { name = name }

This implementation might seem like it’ s different; because in the previous example we did define an interface and as such we can create multiple concrete classes based on this interface, but if you look carefully we’ve defined a function signature CreatePerson which acts like that interface.

If we want to pass a function of a certain type to another function we can even do a type check in the function call:

type Person = { Username: string }

let createPerson name = { Username = name }

let decorator (f:string->Person) (s:string) =
	// please don't do a side effect...
    f s // return value
    
let decoratedCreatePerson = decorator createPerson    

printf "%A" (decoratedCreatePerson "Peter Pan")

In JavaScript we don’t have any way to really check the types, especially those of functions where even the parameters are not fixed. I’m just going to show a little bit of code to show how you could write something like this in JavaScript while having a semblance of safety:

function Person(name) {
	// set your fields and initialize
	this.Name = name;
  
	// now freeze...hammertime...
	return Object.freeze(this);
}

let createPerson = (name) => {
	return new Person(name);
};

let decorator = (f, h) => {
	return (name) => {
		let result = f(name);
		if (!(result instanceof Person) && typeof h === "function") {
			result = h(result);
		}
		return result;
	};
};

let decoratedCreatePerson = decorator(createPerson, (o) => {
	console.log("handle what happens when o is not of type Person.");
	return o;
});

let peterPan = decoratedCreatePerson("Peter Pan");

This JavaScript version is not as tight and simple to understand as the F# version, but it is quite legible and solid. Especially the decorator, which type checks the result of the decoratee, combined with the ES6 lambda notation “feels” like something which is really powerful.

Let’s break this decorator down. The decorator is a function which takes two parameters, f the function which we are going to decorate; and h a function which we’ll use when we have a type error.

What you’ve learned

At the end of this chapter you should have learned the following things:

• Constructors are used to initialize an object.
• We can use an initialization function to create an object.
• Decorators are extremely useful for sticking functionality onto a function.

Decorators are powerful, decorators allow you to wrap functions into more functionality resulting in even more powerful functions.

Monads are Objects

Monads are objects. Don’t get fooled by all the operations which should be possible on these objects to firmly call them monads. In essence, a monad is an object but not every object is a monad, you might say it’s a categorical difference.

In the next chapters I’d like to start with a simple object and add functionality to this object, resulting in a monadic type. As you will notice, the code you will need to write is fairly advanced most of the code is a transformation of functions, but it will be worth it. I can guarantee that you’ll come out a stronger programmer at the end of this document.

Let’s create a type which will serve as the base for our monadic type:

class Monad<T> {
    public readonly T Value;
	public Monad(T t) {
		this.Value = t;
	}
}

These are the beginnings of a Monadic Type, this constructor is a way to create our fledgeling Monad. You may note that this object does nothing more than wrap a value. You should also note that the monad is what we call immutable. After the object is created you cannot change a property of a field. It’s state is fixed.

Word of causion: In .NET you can use reflection to set a readonly field. Doing so is a a very bad idea and there should be no reason to do so. In practice, one of the only reasons you might use refelection to set readonly properties is of third party code where you can’t change the implementation.

When I said that monads are object but not all objects are monads I made a statement which is not easily proven without mathematics. I am going to show mathematical definitions and when possible show some proofs. Monads are objects which wrap around other types. For example, in C# you have Nullable<T> which is a monad.

Every monad must have two functions and the name is function is not important, the signature is!

And:

When reading these type definitions you should realize that the last factor is always the return type, the other factors are always the parameters of the function. This is simply the way we write the types of functions.

As a side note I want to state that in type definitions we write letters for types and capital letters for generic types. So a is a type, for example int or string or Person and Ma is a generic type which wraps the other type, like Nullable<Person> or Maybe<int>.

As you might have deduced, the $lift$ function can be seen as a single parameter constructor where we pass a type and get a type which wraps the original type. This is the way we wrap objects. For example:

var numberList = new List<int> { 12 };

The $bind$ function makes function composition possible. So, for example, when people say that linq is monadic in nature, they mean that we can find the bind signature in the Enumerable.SelectMany function:

public static IEnumerable<TResult> SelectMany<TSource, TResult>(
	this IEnumerable<TSource> source,
	Func<TSource, IEnumerable<TResult>> selector
)

Here IEnumerable<TSouce> is the same as $Ma$ in our $bind$ function. IEnumerable<TResult> is of course $Mb$.

SelectMany takes two parameters, the first one is a source, the second parameter is a function which takes a single item of type TSource and returns an IEnumerable<TSource>. In fact, using SelectMany on, for example, an IEnumerable<int> would return an IEnumerable<IEnumerable<int>> but SelectMany will automatically flatten that to an IEnumerable<int>.

This is the way most explanations work. We start with something really abstract and general like: $f :: a \rightarrow Mb$ and start substituting things like: “$Mb$ is nothing more than IEnumerable<int>” We do this in the hope that you realize that $M$ is a sort of container and $b$ is the type. Eventually we substitute everything with “real examples” hoping that this will clarify the original abstraction. This is the reason why I write almost every example in three programming languages. I hope that one of the three will spark some kind of insight. If you need more clarification I can really advice writing the examples (by hand) in another programming language like for example Clojure, this will certainly deepen your understanding.

The following is a “real world” example of how SelectMany works:

int[] list = {1,2,3,4,5,6,7,8,9};
var numbers = Enumerable.SelectMany(list, (x) => new int[] {x * x});

Func<IEnumerable<int>, string> concat = (xses) => {
	return xses.Aggregate("", (total, x) => 
		total == "" ? x.ToString() : total + "," + x.ToString());
};

var result = concat(numbers);

When we want to explain monads we will first look at the $lift$ and $bind$ functions. After this we’ll look at a few examples and create:

• Identity monad
• Maybe monad
• List monad
• State monad
• Process monad

All of these monad examples should really show why monads are so powerful and how you’d write one yourself if you ever need to.

What you’ve learned

At the end of this chapter you should have learned the following things:

• A monad is nothing more than an object.
• Monads always have at least two functions, a lift and a bind function.
• IEnumerable<T> is a monad and SelectMany is it’s bind function.

When we learn things in this tutorial we usually go from abstract to specific, back to abstract and we’ll use three programming languages to get our point across.

The unit function

Using a constructor is not always the same as functionally passing a value into a container. For all situations where we do not want to use the constructor directly but want to lift a value into our container type we use a unit function.

We will define an operation called unit as an operation which looks a lot like a constructor. There is an entire philosophical reason for calling this function the unit function but we are going to ignore that. What you do need to know is that in Haskell this unit function is called return and it is also sometimes referred to as a lift function although lift is usually reserved for lifting entire functions into the monadic space as we’ll see in another chapter.

I think that the terminology used is one of the most important parts of learning these difficult concepts and learning terminology should be done in three steps:

1. Learn the term
2. Use the term correctly
3. Learn the etymology of the term

We are going to try and follow this path by blindly learning the new term and then using the new term in examples and exercises. At the end of the article we will try and get to the bottom of the origin of the term and figure out what it means.

Let’s define lift:

In C# this unit function would look a lot like:

class Monad<T> {
    public readonly T Value;
	public Monad(T t) {
		this.Value = t;
	}
	
	// lift :: T -> Monad<T>
	public static Monad<T> Lift(T t) {
		return new Monad<T>(t);
	}
}

This Lift function takes a value in type T and returns a value in type Monad<T>. If your language has referential transparency we could even say that:

if (new Monad<int>(12) == Monad<int>.Lift(12)) {
	Console.WriteLine("They are the same!!");
}
else {
	Console.WriteLine("Oh no, C# only cares about pointers!");
}

Definition: A language is referentially transparent if two program fragments that represent the same denotation (and hence “equivalent”) can be exchanged for each other without affecting anything else. It is not the program fragments that are referentially transparent. Referential transparency is a property of the whole language which allows us to replace equivalent fragments by each other. – Uday Reddy

This result here is my first beef with languages like C#. Comparing things is the most basic of operations in a business application and comparing things by reference is not a helpful way to it. We should compare the values inside the objects instead of the references, the pointers.

Let’s look at how this would look in F#; first, here’s the code for our monad:

type Monad<'a> = Value of 'a

The unit function would look something like:

let lift a = Value a

We can use this code by invoking thelift function and matching the result, printing something with the Value:

let m12 = lift 12
match m12 with
| Value n -> printf "Value is: %d" n

The great thing about languages like F# is that we can do:

match Value 12 = lift 12 with
| True -> printf "WOOT!"
| False -> printf "No woot ;("

Not only is the result WOOT!, but I have pattern matched on the result, this means that there are no cases which I’ve missed. This is checked and enforced by the compiler.

Let’s look at the same example but this time let’s use JavaScript. I am not going to write ES6 classes because I personally don’t like them. I really don’t like this syntax which everyone seems to be so comfortable with. Apart from this, a constructor in JavaScript is not a constructor like we know in for example C# or Java. This will most certainly be a subject of another article.

In JavaScript a class is simply a function we write it with a capital letter because sir Crockford taught us that that’s the way to do it. To be honest, style conventions are quite powerful and should not be ignored.

function Monad(value) {
	this.Value = value;
}

function lift(value) {
	return new Monad(value);
}

The lift function is quite simple as well. Because we don’t have a compiler and an enforced type system we can just write what we want.

Just like with C# in JavaScript lift(12) === new Monad(12) will also result in false. This is because JavaScript and C# both check equality by comparing the references, the pointers. These are of course different because they point to different objects. In C# we could override the operator == and != to make sure we compare the Value property:

public class Monad<T> {
    public readonly T Value;
	public Monad(T t) {
		this.Value = t;
	}
	public Monad() {}
	
	public static Monad<T> Unit(T t) {
		return new Monad<T>(t);
	}
	
	public static Func<T, Monad<U>> Map<U>(Func<T,U> f) {
		return (T t) => new Monad<U>(f(t));
	}
	
	public static bool operator == (Monad<T> a, Monad<T> b) {
		return EqualityComparer<T>.Default.Equals(a.Value, b.Value);
	}
	
	public static bool operator != (Monad<T> a, Monad<T> b) {
		return !EqualityComparer<T>.Default.Equals(a.Value, b.Value);
	}
	
	public override bool Equals(System.Object obj) {
        if (obj == null) return false;

        Monad<T> m = obj as Monad<T>;
        if ((System.Object)m == null) return false;

        return this.Value.Equals(m.Value);

    public bool Equals(Monad<T> m) {
        if ((object)m == null) return false;
        return this.Value.Equals(m.Value);
    }
    
    public override int GetHashCode() {
        return this.Value.GetHashCode();
    }
}

But as you can imagine this will become unwieldy very fast. Apart form the fact that we’ve written a lot of code, we only have to check a single value. Imagine having multiple properties….oh the horror! Now imagine adding a property, there is no way for the compiler to know if we’ve checked all the properties. I think it is safe to say that F# is the clear winner when it comes to writing our monadic type and our unit function in a clear and succinct way.

This is my second beef with languages like C#, everything takes so much code to write. It doesn’t matter if you go fully untyped like JavaScript or super typed like F#, you end up with the same functionality but with less code. Less code is not a good thing in and of itself. Readability is very important but I’d like to argue here that what we’ve written is standard F# and as such should be readable by everyone.

The FP community tends to write applications using a lot of x and y for their parameters. I do the same some times. It is important to realize that just as with languages like C#, naming your parameters and functions is every important! Let’s leave the x and y alone and come up with better names.

Up to this point we’ve only seen ways to create an object and pass some data into the constructor. This is neither new nor exiting as far as programming goes. What matters is what this can do. The next chapter will give a small example of using this technique to create a robust system where we can work with data in very solid way.

The Identity Monad

Before we talk about the Identiy Monad we need to talk about complexity in systems. There are many ways of describing complexity in systems but almost everyone agrees that we can fight complexity by designing our application using small parts and combining these parts into bigger parts finally arriving at large systems.

One suck way of combining functionality is by combining functions. The definition of this $combine$ function would look something like:

In C# we could do thing by writing our functionality through delegates and combining these delegates. Imagine the following function:

public static Func<T1, T3> Compose<T1, T2, T3>(Func<T2, T1> f, Func<T3, T1> g) {
	return x => f(g(x));
}

Maybe?

We’ve all had to deal with null reference exceptions in the passed. Maybe we’ve even had applications deployed to production which crashed on a null reference exception. This is really painful because it is a clear programming error. If we had programmed more defensively and checked every object for null this error would not have occurred.

There must be a better way than to litter your code with null checks? There is, if you step into the land of monads you will encounter a pearl, the maybe monad. Look at the next piece of code. I’ve done a few things, the first thing is that I’ve added an empty constructor to the Monad class. The second thing is that I’ve created three new classes: Maybe, Nothing and Just.

The idea behind these classes is that we never return a data object from functions anymore but we always return Maybe<T>. If we do this we can never encounter a null reference exception in our code again!

public class Maybe<T> : Monad<T> {
	public Maybe(T t) : base(t) {}
	public Maybe() {}
}
public class Nothing<T> : Maybe<T> {
	new private T Value;
}
public class Just<T> : Maybe<T> {
	public Just(T t) : base(t) {}
}

How would we use this code? Well imagine querying a database for a user by Id. You don’t know if the user exists or not. (side note: let’s ignore errors for now. The next couple of examples will focus on errors.) When you get your result you want to know for certain if what you got was a user or not. Somehow you want the compiler to catch references to nothing. Here, the Maybe<User> class can help us out. Because we’ve sub-classed Maybe we can upcast or type-check our result and safely continue with the data once we’ve gotten the data.

public class User {
	public readonly string Username;
	public User(string username) {
		this.Username = username;
	}

	// Simulate querying the user from the database.
	// return Just<User> on odd ids
	// return Nothing<User> on even ids
	public static Maybe<User> GetUserById(int id) {
		if (id % 2 == 0) {
			return (Maybe<User>)new Just<User>(new User("Carlos"));
		}
		else {
			return (Maybe<User>)new Nothing<User>();
		}
	}
}

The GetUserById function has the following signature:

So it’s of type:

As you can see, this function is not really the same as the lift function but it does lift a value to a elevated state. I really think that this is the core of all of our problems understanding monads, Functors and other functional jargon. We are so afraid of what is written that we fail to read. We’ve done nothing difficult here, we’ve defined a simple function which instead of returning a User or null we’re returning a Maybe<User>.

But what does it mean? How can we use this code?

var user = User.GetUserById(2);
if (user is Nothing<User>) {
	Console.WriteLine("We got nothing!");
}
else if (user is Just<User>) {
	Console.WriteLine("We got you...." + ((Just<User>)user).Value.Username);
}

You might ask why this is better than simply checking for null. The difference is that in the null check we have lost a bit of our type. In the example using the Maybe class we have to type check in order to get to the Value.

In this previous example you have seen polymorphism at it’s best. This is clear cut example of polymorphism and how it can help you build better software but how would we write this in F#?

type User = { Username: string }

type Maybe<'a> =
	| Just of 'a
	| Nothing

let getUserById id =
    match id % 2 with
    | 0 -> Just { Username = "Carlos" }
    | _ -> Nothing
    
let user = getUserById 2

match user with
| Just u -> printf "We can see you....%s\n" u.Username
| Nothing -> printf "No dice!\n"

There is nothing more to say, F# is the clear winner here in terms of syntax. In C# my inheritance is starting to become unwieldy and in F# we have solved everything by writing a small record, a Discriminated Union and some code which does a little bit of pattern matching. We didn’t even have to implement all of the equality fluff.

Functors

Most tutorials these days pride themselves on the lack of mathematics in the tutorial. I think that learning functional programming in general can be done without learning mathematics in the same way that learning French can be done without learning Latin; but to fully understand the power of functional programming and in this case Monads we will have to write down definitions and these definitions need to be mathematical.

In category theory we have categories which contain objects and morphisms. For now we do not need to dive into these concepts, we will cover them extensively in other parts of this article. What we should know is that an object in category theory is the same as an object in programming. A morphism can be though of as a function.

Now given that we have categories with objects and morphisms, a functor is a structure preserving map between categories. What this means is that a functor should be this:

This simple description states that a functor must be able to map every object in category $C$ to an object in category $D$. This does not mean that every object in $C$ should map to a unique object in $D$, nor does it mean that every object in $D$ should be the target of a mapping. In more mathematical terms: A functor does not have to be a bijective function.

There are two other things which must hold true for Functors. The first is that given a morphism $f :: c \rightarrow c’$ in $C$ there is a morphism $g :: F(x) \rightarrow G(x)$ so that identity and associativity holds true.

We will ignore Identity morphisms for now because they have no non theoretical impact on programming. We should never write a function which returns the parameter exactly as it was. A piece of code like that would be silly, case and point:

function id(x) {
	return x;
}

Associativity is, of course, a different matter. We should write function composition and associativity in the context of Functors look something like:

Assiciativity is really important. Remember the Maybe monad? Associativity would mean that given two functions, for example:

function foo(x) {
	return x * 2;
}

function bar(y) {
    return y * 2;
}

We can combine these functions and really know that the following statement holds true:

new Maybe(foo(bar(2))) === new Maybe(foo( new Maybe(bar(2)) ));

As stated before, these two objects will never be the same in JavaScript because JavaScript resolves equality by looking at the references and not at the values. This might be the single most devastating fact about JavaScript which I can’t seem to resolve or justify.

Map

I hope that the previous example, the Maybe example, convinced you that there is a valid use case for a type like our Monad<T>. But does this mean that we need to rewrite all our code and maybe even all of the code in 3e party libraries in order to use this Monad<T> everywhere? No, that would be really inconvenient and it would even be a bit silly. What we need to do is we need to create some function which lifts our parameters from being normal to being something of type Monad<T>. Luckily we’ve arrived at a chapter which has the name of the function we will need. The map function.

In C# this map function could look something like:

public static Func<Maybe<T>, Maybe<U>> map<T, U>(Func<T, U> f) {
	return (Maybe<T> Mt) => {
		// if we get nothing in, we return nothing...
		if (Mt is Nothing<T>) return new Nothing<U>();
		
		// else we much about with some values and casts and return our value
		U result = f((Mt as Just<T>).Value);
		if (result == null) return new Nothing<U>();
		else return new Just<U>(result);
	};
}

In F# this would look like:

let map f =
	fun Ma ->
		match Ma with
		| Nothing -> Nothing
		| Just a ->
			Just (f a)

The main difference is that in F# we can never have a function return null, so the need for the Maybeclass is less. The way in F# you return nothing is by using the Option type which is exactly the same as the Maybe type we just created.

Something

Bind

The bind function has the following signature:

SAMPLE

using System;
using System.Linq;
		
// Our little monad class.
abstract class Monad<T> {
	public readonly T Value;
	public Monad() {}
	public Monad(T t) {
		this.Value = t;
	}
}

// Our abstract Maybe class, used as the root of
// the Just and Nothing branches.
abstract class Maybe<T> : Monad<T> {
	public Maybe() : base() {}
	public Maybe(T t): base(t) {}
}
// Indicates we have a value.
sealed class Just<T> : Maybe<T> {
	public Just(T t) : base(t) {}	
}
// indicates we have nothing.
sealed class Nothing<T> : Maybe<T> {
	public Nothing() : base() {}
}


public class Program
{
	
	private static Func<int, Maybe<int>> getNumber = (int x) => {
		if (x % 2 == 0) {
			return (Maybe<int>)new Just<int>(x);
		}
		else {
			return (Maybe<int>)new Nothing<int>();
		}
	};
	
	private static Maybe<T> print<T>(Maybe<T> m) {
		if (m is Just<T>) {
			Console.WriteLine("Your number is: " + (m as Just<T>).Value.ToString());
		} else {
			Console.WriteLine("This is not a number");
		}
		return m;
	}
	
	private static Func<int, Maybe<int>> compose = (int x) => {
		return print(getNumber(x));
	};
	
	
	public static void Main()
	{
		// simple example where we query the numbers
		// and use a linq query to process the numbers and 
		// get the result...
		int[] numbers = { 1,2,3,4,5,6,7,8,9,10 };
		var nm = from n in numbers 
				 select compose(n);
		nm.ToList();
	}
}