Monday, May 30, 2016

What's in a Monad?

Over the last few months I’ve progressed from the basics of functional programming to writing real-life, production code in F#. Inevitably, the concept of monads has come up.

Trying to learn what these slippery things are has been tough. The tutorials out there range from a lovely pictorial representation of Haskell monads to an example-driven series showing how common C# types are in fact monads to focusing on the actual functions that monads have in F#.

It’s fair to say that no single article or ever series of posts made me sit up and think ‘ah, so that’s what a monad is!’, which seems to tally with other people’s experience. For me, what made things click was asking the right question:

Why do we have monads?

Back to the start

It sounds a little strange when you put it like this, but so much of what I initially read on the topic focused on more esoteric questions that, to me, didn’t get to the crux of the matter, things like:

  • What is a monad?
  • What are the monad laws?
  • What does [insert monad name here] look like in Haskell/F#/…

I wanted to know why. Something must have driven computer scientists to look at category theory and think ‘maybe these will help us write programs!’

To understand this reasoning, I went back to the start. This meant reading the original paper that introduced monads back in 1996.

If this sounds scary to you, I don’t blame you, but bear with me. The paper is so nicely written and well explained that it made a huge difference to my understanding, and finally got my brain to connect the dots.

It did this by starting with a problem, and ending with the solution. So when I sat down to write my first production F# code, and I immediately came across a very similar problem, I already knew what the answer was.

In this post, I’m going to walk you through not only how I used monads to solve a real-world programming problem, but also say why they are such a good fit for the solution technique

This is going to be in three sections:

  • What is the problem we want to solve
  • How to we normally solve it in an object-oriented or imperative fashion
  • How can monads help us solve it more functionally?

A Common Problem

I write financial applications, and wanted a way for someone to select some asset data in Excel and send it to a central database. In more detail, this meant:

  • getting the input from a user through an ExcelDNA function;
  • validating that the input was correctly formed;
  • checking the exsiting database for similar records;
  • checking that links to other applications were valid; and
  • posting the data to the database

I realised quickly that this looked pretty similar to an example on Scott Wlaschin’s site, in which he uses the Either Monad to do something pretty similar, using the concept of a railway to explain things.

First though, I’ll outline how we would typically solve this in an imperative fashion, using C# as an example.

The Imperative Approach

In C#, this kind of thing might typically be done like this:

    [ExcelFunction (IsMacroType = true)]
    public static object StoreAssetData ([ExcelArgument] object [,] inputAllocation)
        bool isValid = ValidateInput (inputAllocation);

        if (!isValid) 
            return ExcelError.ExcelErrorValue;

        bool similarDataAlreadyExists;
            similarDataAlreadyExists = CheckExistingDatabase (inputAllocation);
            return ExcelError.ExcelErrorValue;

            return ExcelError.ExcelErrorValue

        bool linksToOtherAppsAreValid;
            linksToOtherAppsAreValid = CheckOtherServices (inputAllocation);
            return ExcelError.ExcelErrorValue;

        if (!linksToOtherAppsAreValid) 
            return ExcelError.ExcelErrorValue;

            return ExcelError.ExcelErrorValue;

        return "Done!";

To me, there are a couple of problematic areas here. First, the control flow is hard to follow, and we keep getting forced to return early from the method if one bit fails. Second, operations that might throw exceptions need to be wrapped in fairly generic try-catch blocks, with the result of those operations defined outside of the block to be accessible elsewhere. Third, your focus is lost amongst the outline of the curly braces and you can’t easily figure out what the method wants to do.

Specifics aside, the imperative style looks at the core operations as then rather than and. That is, we are saying ‘validate this, then check that, then do this’, which has the problem that we need to check what state we’re in after each operation.

From a logical standpoint, we want to be able to say ‘validate and check and…’, and once it’s all done, tell me if it’s worked or not.

To do this, we need composition.

How Do Monads Help?

As scary as they sound, monads are exactly about this kind of things — composition, chaining, pipelining, and all these good functional things.

To help with our problem we need to be able to do a couple of very specific things:

  • Parallel composition: in this example we’ve got an array of entries to validate. Ideally we want to check every column of every row and tell the user about all of their mistakes, not just the first one.
  • Sequential composition: here we’ve got several steps that check for inconsistencies with existing data. However, if the data input to the function is malformed then there’s no point in doing this so we want some way of ‘skipping’ certain steps if previous ones failed (without exiting early from the routine and proliferating our curlies)
  • Result extraction: we want to get right to the end of the method and be able to say ‘this is the result’. Moreover if it’s not good news, we want to have as much information to give to the user about what went wrong as we can.

Fortunately, it turns out that we can do all of this with monads.

Briefly Introducing Result

type Result<'TSuccess, 'TFailure> = 
    | Success of 'TSuccess
    | Failure of 'TFailure

Here’s the type that we will be using to ease all of our pains. The idea is simple: the result of doing something is either Success or Failure, and in each case we include some data — the success case carries the input data that we want to feed to the next operation, and the failure case carries error messages.

This is beautiful in its simplicity and actually gives us everything we wanted. We have a way to compose operations that are successful by passing whatever we want in the success case, and a way to signal prior failure by passing through error messages in our failure wrapper

All we need to do now is see exactly how this composition works.

Parallel Composition: apply

let plusResult addSuccess addFailure result1 result2 = 
    match result1, result2 with
    | Success x1, Success x2 -> Success(addSuccess x1 x2)
    | Failure y1, Success _ -> Failure y1
    | Success _, Failure y2 -> Failure y2
    | Failure y1, Failure y2 -> Failure(addFailure y1 y2)

let apply f result = plusResult id (@) f result

let (<*>) = apply

Composing things in parallel is done with apply. In English, we take the results of two things (result1 and result2, each of which will either be Success or Failure), and say what to do in each of the possible cases:

  • If we’ve got two successes, return whatever was in the first case using the identity function id.
  • If we’ve got one failure and one success, return the Failure along with its error data.
  • If we’ve got two failures, return a new Failure with the error messages from each concatenated using infix list concatenation (@).

The infix version <*> is handy for neatening up the syntax, so we can write f1 <*> f2 <*> f3 rather than apply f1 (apply f2 f3).

Sequential Composition: bind

let either successFunc failureFunc = 
    | Success x -> successFunc x
    | Failure y -> failureFunc y

let bind f = either f Failure

let (>>=) x f = bind f x

This is even easier: we are passing in something to a function, if the thing is Success then apply the function to do data within, if it’s Failure then return the existing error messages.

Result Extraction: either

Getting the result out at the end of our computation is simply a more general case of sequencing things together — we do what we did for bind but allow the user to pass in whatever success or failure functions they want.

This has other benefits, for example testing — let’s say that in production we want a popup displaying either the error message or a happy success one. When we test, we’ve already abstracted the nasty UI/popup concerns and can inject our own tests implementations.

Putting It Into Practice

It looks like we’ve got the pieces that we need — and I haven’t even had to mention the monad laws! It’s deceptively simple stuff once you boil it down to exactly why you need each individual part of a monad.

And so to an actual solution. This is how we read our raw input rows contianing data:

let getRows (rows : obj [,]) = 
    seq { 
        for i in 0..(rows.GetLength(0) - 1) do
            let asset = readRow rows.[i, *]
            match asset with
            | Success x -> yield Success x
            | Failure failureMessages -> 
                yield Failure(sprintf "Row %d has problems: " i + String.concat "; " failureMessages)

For each row, we read it. If the data is good, we yield it. If it’s not, we aggregate all the failure messages that we got back from reading it and yield a new one with some more contextual information.

Here’s how we read a single row:

let readRow (row : obj []) = 
        let createAsset displayName portfolioName marketValue collateral Fund Strategy = 
        { DisplayName = displayName
          PortfolioName = portfolioName
          MarketValue = marketValue
          CollateralClassification = collateral
          FundName = Fund
          StrategyName = Strategy }
    Success createAsset 
    <*> getString [ "DisplayName was missing or empty" ] row.[DisplayNameColumn] 
    <*> getStringOption row.[PortfolioNameColumn] 
    <*> getDouble [ (sprintf "MarketValue (%O) was not a valid number" row.[MarketValueColumn]) ]  row.[MarketValueColumn] 
    <*> getStringOption row.[CollateralColumn] 
    <*> getStringOption row.[FundColumn]
    <*> getStringOption row.[StrategyColumn]

We use the infix version of apply to read each column in turn and aggregate any problems we may have together. The helper functions getString, getStringOption and getDouble do pretty much what you would expect — they take an individual element of the input array and if they are of the desired type return Success, otherwise they return Failure with the injected error message.

We combine these with our result creation using bind:

let readAssetData inputAssetData = 
|> getRows
|> foldResults
>>= createAssetData

where the createAssetData function is just a factory method to format the result, and foldResults simply combines the sequences yielded by getRows into one.

To spice things up a little, extracting the result can be done in C# by calling into the either function (in F#) we saw earlier:

public static class ResultExtensions
    internal static TResult Result<TSuccess, TFailure, TResult>(
        this Result<TSuccess, TFailure> twoTrackInput,
        Func<TSuccess, TResult> successFunc,
        Func<TFailure, TResult> failureFunc)
        var sucessConverter = new Converter<TSuccess, TResult>(successFunc);
        var failureConverter = new Converter<TFailure, TResult>(failureFunc);

        var onSuccess = FSharpFunc<TSuccess, TResult>.FromConverter(sucessConverter);
        var onFailure = FSharpFunc<TFailure, TResult>.FromConverter(failureConverter);

        var result = either(onSuccess, onFailure, twoTrackInput);

        return result;

This is a little verbose but shows how the language interop works, and means that we can use higher-order fucntions in C# (yay!) to do things like logging and error handling.

Adding logging

Let’s say we want to add logging to our application. We could use something like aspect-oriented programming and bring in loads of heavyweight third-party frameworks, or we could use monads:

    public static readonly Func<string, object> LogFailure = errorMessage =>
        return ExcelError.ExcelErrorValue;

This function is passed into Result as the failureFunc parameter, and magically logs all of our failure messages!

Wrapping Up

In this post we’ve seen how a common imperative solution to a standard business problem can be transformed into something much neater and more scalable using some functional programming concepts.

The fact that these concepts have their roots in semi-obscure mathematical theory should not put you off using them — to see this, begin with the why.

Ask yourself why monads are useful, and with a bit of reading you will figure it out. Then next time you see a problem like this one, you’ll know exactly what to do.

No comments:

Post a Comment