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
Return: 'a -> M<'a>
Bind: M<'a> -> ('a -> M<'b>) -> M<'b>

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
// Note that type annotations are optional. I made them explicity for clarity.
type Maybe<'a> =
    | Just of 'a
    | Nothing

let Return (x: 'a) : Maybe<'a> =
    Just(x)

let Bind (mx: Maybe<'a>) (f: 'a -> Maybe<'b>) : Maybe<'b> =
    match mx with
    | Just(x) -> f x
    | Nothing -> Nothing

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
type ParserResult<'a> =
    | Success of 'a * list<char>
    | Failure

type Parser<'a> = list<char> -> ParserResult<'a>

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
let Return (x: 'a): Parser<'a> =
    let p stream = Success(x, stream)
    in p

let Bind (p: Parser<'a>) (f: 'a -> Parser<'b>) : Parser<'b> =
    let q stream =
        match p stream with
        | Success(x, rest) -> (f x) rest
        | Failure -> Failure
    in q

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

1
let (>>=) = Bind

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
/// If parser p succeeds, returns x as a result.
let (>>%) p x : Parser<'b> =
    p >>= (fun _ -> Return x)

/// Applies parsers p1 and p2, returning the result of p2.
let (>>.) p1 p2 : Parser<'b> =
    p1 >>= (fun _ -> p2)

/// Applies parsers p1 and p2, returning the result of p1.
let (.>>) p1 p2 : Parser<'a> =
    p1 >>= (fun x -> p2 >>% x)

/// Applies parsers p1 and p2, returning both results.
let (.>>.) p1 p2: Parser<'a*'b> =
    p1 >>= (fun x -> p2 >>= (fun y -> Return (x, y)))

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 >>= operations.

Workflows

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 Return and Bind as you might have guessed. This is how we can define the parse workflow:

1
2
3
4
5
6
// Note that we previously defined Bind and Return.
type ParserBuilder() =
    member x.Bind(p, f) = Bind p f
    member x.Return(y) = Return y

let parse = new ParserBuilder()

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
// This is the Either combinator defined in the previous blog post.
let (<|>) = Either

let rec Many p : Parser<list<'a>> =
    parse {
        let! x = p          // Applies p
        let! xs = (Many p)  // Applies (Many p) recursively
        return x :: xs      // returns the cons of the two results
    } <|> Return []

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
let Many1 p : Parser<list<'a>> =
    parse {
        let! x = p          // Applies p
        let! xs = (Many p)  // Applies (Many p) recursively
        return x :: xs      // returns the cons of the two results
    }

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
/// Parses float numbers which match /[+-]?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?/
let FloatParser: Parser<float> =
    parse {
        let! s = (CharParser '+' <|> CharParser '-') <|> Return '+'     // [+-]?
        let! l = (parse {                                               // (
            let! l = Many1 DigitParser                                  //   \d+
            let! pd = (parse {                                          //   (
                let! p = CharParser '.'                                 //     \.
                let! d = Many DigitParser                               //     \d*
                return p::d
                } <|> Return [])                                        //   )?
            return l @ pd
            } <|>                                                       //   |
            parse {
                let! l = Many DigitParser                               //   \d*
                let! p = CharParser '.'                                 //   \.
                let! d = Many1 DigitParser                              //   \d+
                return l @ p::d
            }                                                           // )
        )
        let! e = (parse {                                               // (
            let! e = CharParser 'e' <|> CharParser 'E'                  //   [eE]
            let! s = (CharParser '+' <|> CharParser '-') <|> Return '+' //   [+-]?
            let! x = Many1 (DigitParser)                                //   \d+
            return e::s::x                                              // )?
        } <|> Return [])
        return float (new System.String(s::(l @ e) |> List.toArray))
    }

which allows us to do the following parsing:

1
2
> printfn "%A" (FloatParser ("-1.23e45" |> Seq.toList));;
Success (-1.23e+45,[])

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 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.

Comments