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:
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
1 2 3 4 5 6 7 8 9 10
TA-DAA! There’s a monad. It is standard notation, though, to use the operator
>>= for the
Bind operation. We can define it too:
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 do-notation (perform-notation in OCaml or computation expressions in F#), which is a syntactic sugar that tries to mimick the imperative-style laguages. Basically, it allows you to write a series of simple statements instead of a nested series of
In order to use the F#’s equivalent to the do-notation, 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
Bind as you might have guessed. This is how we can define the
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
+ 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:
Imagine if we had to write the previous parser with nested
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 do-notation would be a pain in the ass.
All the code snippets are available here for easy access and testing.
Wow, that was long.