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
We can now define our functions that should have the implicit log context:
We execute g with:
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.
Understanding Monads comes from practice
This topic is intended for intermediate to advanced F# developers
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.
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:
Tying it all together:
Running it all in FSI:
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:
This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0