Monads in F#
When I first tried to learn what monads were, I probably made the mistake of going to wikipedia, which only made things worse. It was not until I began to play with parser combinators that I started to grasp the concept.
What are monads?
You probably heard the word monad if you have dealt with functional programming. However, to me the word is rather obscure, and might sound a little daunting to people starting in functional programming. This is one of the reasons why the creators of F# decided to avoid this term and use the word workflow or computation expression instead.
Ok… but what are they?
Basically, monads are just a typeclass and two fundamental operations associated. Think of a generic interface with two abstract methods. These operations have the following syntax:
1 2 

If you have a type M<'a>
and two methods with those signatures, then you’ve got a monad. (Actually there are a couple rules these two methods must obey, but we will skip them since they might complicate things.)
The classical example is the Maybe/Option monad. In F#, it can be defined as follows:
1 2 3 4 5 6 7 8 9 10 11 12 

which may suffice within the pages of a textbook, but it didn’t make things any clearer to me. Instead, I am going to explain how the usage of monads makes a lot of sense when dealing parser combinators. (If you want to keep reading about the Maybe monad example you can go to the wikipedia entry about monads).
Monads and parser combinators
If you don’t know what parser combinators are, you can read my previous blog post to get a quick overview.
So we have the following type definition:
1 2 3 4 5 

That means that a Parser
is just a function that takes a list of characters and returns a ParserResult<'a>
, which can be either a Failure
if nothing could be parsed or a Success
otherwise, returning both the parsed element and the rest of the list.
Now that we have the typeclass Parser
, we only need to define the associated Return
and Bind
operations:
1 2 3 4 5 6 7 8 9 10 

TADAA! There’s a monad. It is standard notation, though, to use the operator >>=
for the Bind
operation. We can define it too:
1


Cool, but how is this useful?
Those functions we just defined allow us to define the following parser combinators in a very concise way:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

Notice that the Bind operator >>=
is used twice in the definition of the .>>.
operator. Unfortunately, this gets harder to read as the complexity of parsers increases. This is why Haskell introduced the donotation (performnotation in OCaml or computation expressions in F#), which is a syntactic sugar that tries to mimick the imperativestyle laguages. Basically, it allows you to write a series of simple statements instead of a nested series of >>=
operations.
Workflows
In order to use the F#’s equivalent to the donotation, we need to create a workflow builder. Workflow builders are just an interface that we have to implement. Two methods are required; the rest are optional. These two methods are Return
and Bind
as you might have guessed. This is how we can define the parse
workflow:
1 2 3 4 5 6 

and this is how we use it to define the Many
parser combinator in a more readable way than thre previous blog post.
1 2 3 4 5 6 7 8 9 

or the following Many1
combinator, which is similar to the Many
combinator but requires at least one success (Think of *
vs +
in regular expressions):
1 2 3 4 5 6 

or even more complex parsers such a this floating point number parser:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 

which allows us to do the following parsing:
1 2 

Imagine if we had to write the previous parser with nested >>=
operators…
Conclusion
I think we can summarize the post in the following points:
 The word monad is cool but gives no clue of what they actually are. Other languages have chosen more descriptive names such as workflows.
 A monad is just an interface with certain rules in the implementation of its methods.
 Parser combinators are a good example of the usage of monads.
 Monads without the donotation would be a pain in the ass.
All the code snippets are available here for easy access and testing.
Wow, that was long.