# Monads

## Computation Expressions provide an alternative syntax to chain Monads

Related to Monads are `F#`

computation expressions
(`CE`

). A programmer typically implements a `CE`

to provide an alternative approach to chaining Monads,
ie instead of this:

You can write this:

Both styles are equivalent and it's up to developer preference which one to pick.

In order to demonstrate how to implement a `CE`

imagine you like all traces to
include a correlation id. This correlation id will help correlating traces
that belong to the same call. This is very useful when have log files that
contains traces from concurrent calls.

The problem is that it's cumbersome to include the correlation id as an argument to all functions. As Monads allows carrying implicit state we will define a Log Monad to hide the log context (ie the correlation id).

We begin by defining a log context and the type of a function that traces with log context:

We also define two trace functions that will log with the correlation id from the log context:

`trace`

is a `Function<unit>`

which means it will be passed a log context when invoked.
From the log context we pick up the correlation id and traces it together with `v`

In addition we define `bind`

and `return_`

and as they follow the
Monad Laws this forms our Log Monad.

Finally we define `LogBuilder`

that will enable us to use `CE`

syntax to chain
`Log`

Monads.

We can now define our functions that should have the implicit log context:

We execute g with:

Which prints:

Notice that the CorrelationId is implicitly carried from `run`

to `g`

to `f`

which
allows us the correlate the log entries during trouble shooting.

`CE`

has lot more features
but this should help you get started defining your own `CE`

:s.

Full code:

## Understanding Monads comes from practice

*This topic is intended for intermediate to advanced F# developers*

"What are Monads?" is a common question. This is easy to answer but like in Hitchhikers guide to galaxy we realize we don't understand the answer because we didn't know what we were asking after.

Many believe the way to understanding Monads is by practicing them. As programmers we typically don't care for the mathematical foundation for what Liskov's Substitution Principle, sub-types or sub-classes are. By using these ideas we have acquired an intuition for what they represent. The same is true for Monads.

In order to help you get started with Monads this example demonstrates how to build a Monadic Parser Combinator library. This might help you get started but understanding will come from writing your own Monadic library.

**Enough prose, time for code**

The Parser type:

Using this definition of a Parser we define some fundamental parser functions

`satisfy`

is a function that given a `sat`

function produces a parser that succeeds if we haven't passed `EOS`

and the character at the current position passes the `sat`

function. Using `satisfy`

we create a number of useful character parsers.

Running this in FSI:

We have some fundamental parsers into place. We will combine them into more powerful parsers using parser combinator functions

The names and signatures are not arbitrarily chosen but we will not delve on this, instead let's see how we use `bind`

to combine parser into more complex ones:

What this shows us is that `bind`

allows us to combine two parsers into a more complex parser. As the result of `bind`

is a parser that in turn can be combined again.

`bind`

will be the fundamental way we combine parsers although we will define helper functions to simplify the syntax.

One of the things that can simplify syntax are computation expressions. They are easy to define:

FSI

This is equivalent to:

Another fundamental parser combinator we are going to use alot is `orElse`

:

This allows us to define `letterOrDigit`

like this:

**A note on Infix operators**

A common concern over FP is the use of unusual infix operators like `>>=`

, `>=>`

, `<-`

and so on. However, most aren't concerned over the use of `+`

, `-`

, `*`

, `/`

and `%`

, these are well known operators used to compose values. However, a big part in FP is about composing not just values but functions as well. To an intermediate FP developer the infix operators `>>=`

, `>=>`

, `<-`

are well-known and should have specific signatures as well as semantics.

For the functions we have defined so far we would define the following infix operators used to combine parsers:

So `>>=`

means `bind`

and `<|>`

means `orElse`

.

This allows us combine parsers more succinct:

In order to define some advanced parser combinators that will allow us to parse more complex expression we define a few more simple parser combinators:

We are ready to define `many`

and `sepBy`

which are more advanced as they apply the input parsers until they fail. Then `many`

and `sepBy`

returns the aggregated result:

**Creating a simple expression parser**

With the tools we created we can now define a parser for simple expressions like `1+2*3`

We start from the bottom by defining a parser for integers `pint`

We try to parse as many digits as we can, the result is `char list`

. If the list is empty we `fail`

, otherwise we fold the characters into an integer.

Testing `pint`

in FSI:

In addition we need to parse the different kind of operators used to combine integer values:

FSI:

Tying it all together:

Running it all in FSI:

**Conclusion**

By defining `Parser<'T>`

, `return_`

, `bind`

and making sure they obey the monadic laws we have built a simple but powerful Monadic Parser Combinator framework.

Monads and Parsers go together because Parsers are executed on a parser state. Monads allows us to combine parsers while hiding the parser state thus reducing clutter and improving composability.

The framework we have created is slow and produces no error messages, this in order to keep the code succinct. FParsec provide both acceptable performance as well as excellent error messages.

However, an example alone cannot give understanding of Monads. One has to practice Monads.

Here are some examples on Monads you can try to implement in order to reach your won understanding:

- State Monad - Allows hidden environment state to be carried implicitly
- Tracer Monad - Allows trace state to be carried implicitly. A variant of State Monad
- Turtle Monad - A Monad for creating Turtle (Logos) programs. A variant of State Monad
- Continuation Monad - A coroutine Monad. An example of this is
`async`

in F#

The best thing in order to learn would be to come up with an application for Monads in a domain you are comfortable with. For me that was parsers.

Full source code: