Much Ado About Monads – Maybe Edition

In the past I’ve extensively talked about creating monads, but not as much more around them in terms of why you might use them and what problems they are trying to solve.  Since that time, I’ve been challenged by others to actually prove not only that it can be understood by everyone, but they are very useful as well.  It’s been a form of geekery among us software professionals to say, “Whoopee! I’ve learned how to implement a monad to do x” without really explaining the reason why people should care. 

This series of posts is set to dispel some of those qualms people have with the word monad and why it might be useful in other languages besides Haskell, from which the term in the computer science world came.  In the past here, I’ve talked extensively about them, so I won’t necessarily bore you with the excruciating details, but I still have to answer the question in a brief and to the point answer, what exactly is a monad anyways?

 

What is a Monad?

For those not really interested in category theory and such, let’s get to a basic definition instead.  Think of it as a basic abstract data type used to represent computations.  We can abstract away complex behavior, such as IO actions, asynchronous behavior uniformly in such a way that we can sequence these operations together.  Here’s the best definition of all, “We can abstract the complicated things out of the way so that we can write a program that we want to read it instead of how it really works”.  I’d rather see the focus not on the category theory part, as that is interesting and a key to what’s going on here, but instead as a nice design pattern for abstracting complexity.

Now the question arises, how and when do we use them?  When does it make sense?  To understand that, we need to look at the problems we’re facing.  Let’s take an example of chaining conditionals together which may or may not succeed.

 

What’s the Problem?

To really understand why it’s useful, we first have to understand the problem we’re trying to solve.  As I stated above, let’s first take a look at chaining together conditional operations which may or may not succeed.  Let’s take for example a series of lookups against some hash tables in a way where one lookup depends on another.  Typically in C#, our code might look like the following.  It’s naive code in terms of the style but I’ve seen this pattern time and time again in code:

class Program
{
    private static readonly Dictionary<string,string> employeeDept = 
        new Dictionary<string, string>
                               {
                                   {"John", "Sales"},
                                   {"Bob", "IT"}
                               };
    private static readonly Dictionary<string, string> deptCountry = 
        new Dictionary<string, string>
                              {
                                  {"IT", "USA"},
                                  {"Sales", "France"}
                              };
    private static readonly Dictionary<string, string> countryCurrency = 
        new Dictionary<string, string>
                                 {
                                     {"USA","Dollar"},
                                     {"France","Euro"}
                                 };

    public static string GetEmployeeCurrency(string name)
    {
        string dept;
        string country;
        string currency;
        
        if(!employeeDept.TryGetValue(name, out dept))
            return null;

        if(!deptCountry.TryGetValue(dept, out country))
            return null;

        return !countryCurrency.TryGetValue(country, out currency) 
            ? null : currency;
    }

    static void Main(string[] args)
    {
        var johnCurrency = string.Format("John's currency: {0}"
            GetEmployeeCurrency("John"));
        var peteCurrency = string.Format("Pete's currency: {0}",
            GetEmployeeCurrency("Pete"));

        Console.WriteLine(johnCurrency);
        Console.WriteLine(peteCurrency);
    }
}

As you’ll notice from the above code, we have three dictionaries of various information that we’re using as lookups.  And you’ll also note that we have to go through a bit of hassle just to determine if one’s in a list, and if so, continue onto the next.  Similarly, in F#, we run into that same issue as well, with an example of how that could be a problem.

let employeeDept = Map.of_list([("John","Sales"); ("Bob","IT")]) 
let deptCountry = Map.of_list([("IT","USA"); ("Sales","France")]) 
let countryCurrency = Map.of_list([("USA", "Dollar"); ("France", "Euro")]) 

let employeeCurrency name = 
  match Map.tryfind name employeeDept with 
  | None      -> None 
  | Some dept -> 
      match Map.tryfind dept deptCountry with 
      | None         -> None 
      | Some country ->  
          Map.tryfind country countryCurrency

let johnCurrency = sprintf "John's currency: %A" (employeeCurrency "John")
let peteCurrency = sprintf "Pete's currency: %A" (employeeCurrency "Pete")
 

And indeed, you could run into this pattern as well in Haskell without trying really hard either:

import qualified Data.Map as M

employeeDept :: M.Map String String
employeeDept = M.fromList([("John","Sales"), ("Bob","IT")])

deptCountry :: M.Map String String
deptCountry = M.fromList([("IT","USA"), ("Sales","France")])

countryCurrency :: M.Map String String
countryCurrency = M.fromList([("USA", "Dollar"), ("France", "Euro")])

employeeCurrency :: String -> Maybe String
employeeCurrency name = 
  case M.lookup name employeeDept of
      Nothing -> Nothing
      Just dept ->
        case M.lookup dept deptCountry of
            Nothing -> Nothing
            Just country ->
              M.lookup country countryCurrency
 

Just watch that code walk off the screen to the right!  Are you starting to notice a pattern here?  I sure am!  Now the question arises, what can we do about it?  How can we write the code the way it should look instead of all the conditional logic we’ve had to bake in.  Wouldn’t you rather write it something like this?

// Pseudocode F#
let employeeCurrency name =
  let dept = Map.tryfind name employeeDept
  let country = Map.tryfind dept deptCountry
  Map.tryfind country countryCurrency
 

Through the power of monads, we can, at least something very similar to this.  So, let’s find out how.

 

Introducing Monads

Monads are a concept in the computer science field to come from the Haskell programming language.  Most people assume, oh, it’s only used for IO, but that’s simply not true at all.  Instead, we can treat it as a common abstraction to solve any number of problems, including the conditional logic from above which may succeed or fail.

To create this abstraction, Haskell has a Monad type class which allows us to generalize the application of them.  Let’s look at exactly what that looks like:

class Monad m where
  -- Sequentially compose two actions
  -- passing any value produced from the first to the next
  (>>=) :: m a -> (a -> m b) -> m b
  
  -- Sequentially compose two actions
  -- discarding any value produced from the first

  (>>) :: m a -> m b -> m b
  
  -- Inject a value into the monadic type
  return :: a -> m a
  
  -- Fail with a message
  fail :: String -> m a
 

I added comments to each function that the type class implements to give you an idea about what each one of them does.  What’s our ultimate goal here?  Well, it’s the ability to string together functions that may or may not succeed and to sequence these instructions together.  With an implementation of a monad, we get that ability.

Now, let’s move onto the Maybe implementation.  What is maybe anyways?  It’s a simple algebraic data type which allows for just a value or no value at all such as this:

data  Maybe a  =  Nothing | Just a
  deriving (Eq, Ord)
 

Now that we understand that, let’s move onto looking at the monad instance for the Maybe type.

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

    (Just _) >>  k      = k
    Nothing  >>  _      = Nothing

    return              = Just
    fail _              = Nothing

These are defined in the base class libraries in Haskell, so there is no need to implement this yourself.  What this allows us to do is simply our code dramatically.  Let’s look at the sugared and de-sugared examples:

-- Imperative style
employeeCurrency' :: String -> Maybe String
employeeCurrency' name = do
  dept <- M.lookup name employeeDept
  country <- M.lookup dept deptCountry
  M.lookup country countryCurrency

-- De-sugared version on one line
employeeCurrency'' :: String -> Maybe String
employeeCurrency'' name = 
  lookup employeeDept name >>= lookup deptCountry >>= lookup countryCurrency
  where lookup = flip M.lookup
 

Wow, looks much nicer!  How, you say?  Because we get to see the code as we’d like to read it, as a script instead of a bunch of nested if statements.  But, how does this apply to F# and other .NET languages?  The answer is actually simple and straight forward.

 

Maybe F#?

Now that we understand some of the basics and how it can be done in Haskell.  Let’s translate these ideas to F#.  First, we need to consider the Option type, which is a similar implementation to the Haskell Maybe type.  Knowing what we’ve learned in previous posts on my blog about how monads can be implemented, let’s look at a standard F# implementation. 

[<AutoOpen>]
module MaybeMonad =  
  let bindM x k =
    match x with
    | Some x -> k x
    | None   -> None
    
  let returnM x = Some x

type MaybeBuilder() =
  member x.Bind(x, k) = bindM x k
  member x.Return(x)  = returnM
  member x.Delay(f)   = f()

When we define a builder such as we’ve done above, we now have the ability to use the syntactic sugar to wrap our code up in blocks rather nicely.  This is a bare implementation of the monad, as I could add additional features such as support for using bind statements and such.  The Expert F# book walks through this in detail in the Language Oriented Programming section.  We could use either the sugared or de-sugared versions if we do a little bit of work on our part to make this happen.  Let’s see how we implement this behavior to get what we want:

// Sugared syntax
let maybe = new MaybeBuilder()
let employeeCurrency' name =
  maybe { let! dept = Map.tryfind name employeeDept
          let! country = Map.tryfind dept deptCountry
          return! Map.tryfind country countryCurrency
        }
  
let johnCurrency' = 
  sprintf "John's currency: %A" (employeeCurrency' "John")
let peteCurrency' = 
  sprintf "Pete's currency: %A" (employeeCurrency' "Pete")    
  
// Desugared syntax
let flip f x y =  f y x
let (>>=) = bindM
let employeeCurrency'' name =
  let lookup = flip Map.tryfind
  lookup employeeDept name >>= lookup deptCountry >>= lookup countryCurrency 
     
let johnCurrency'' = sprintf "John's currency: %A" (employeeCurrency'' "John") 
let peteCurrency'' = sprintf "Pete's currency: %A" (employeeCurrency'' "Pete") 
 

This gives us the flexibility we need as programmers to use whichever abstraction we see fit.  Unfortunately, due to type classes not really being something you can easily do in F#, we had to take some liberties with the bind operator and so on.  As an imperative programmer, the sugared syntax makes absolute sense about what I’m trying to accomplish.  It reads much like a script and to not have to worry about the noise associated with nested if statements littering the codebase.

And yes, you could use the lessons from my Functional C# libraries on MSDN Code Gallery to also implement this in C#, as I’ve covered in the past.  With the careful use of extension methods and a little know how, you too can write LINQ statements such as this to determine whether an employee’s currency can be found.  As I’ve said earlier, you can use the LINQ syntax to do things that don’t deal with collections at all, such as this:

public static Maybe<string> GetEmployeeCurrency(string name)
{
    return from dept in employeeDept.TryFind(name)
           from country in deptCountry.TryFind(dept)
           from currency in countryCurrency.TryFind(country)
           select currency;
}
 

The more you keep working with these abstractions, the more you’ll understand how to use them and where they apply.  For further reading, I always recommend the Real World Haskell book which goes over these design patterns in detail.

 

Conclusion

Now, I think through this careful exploration, you may have a better understanding of these design patterns or at least how you might be able to abstract some sort of uniform complexity.  There’s more to these patterns than just the maybe, as there’s the ever so familiar list and error, but also some interesting ones that are unique to F# in the async “workflow”.  What I’m really trying to drive home here is that ideas from functional programming aren’t just for guys in lab coats or those at the universities, but for general line of business developers as well.  Stepping out of that comfort zone that is C# or VB and into a more functional language will give you a greater appreciation of different styles and improve your day to day coding.



kick it on DotNetKicks.com
Published Wednesday, January 28, 2009 5:51 PM by podwysocki

Comments

# re: Much Ado About Monads – Maybe Edition

Thursday, January 29, 2009 4:52 PM by Matt Monad

I don't know too much about programming, but if you like monads, check out our website for some tunes.

www.themonads.com

# re: Much Ado About Monads – Maybe Edition

Friday, January 30, 2009 9:32 AM by Damien

Im sorry, but this transformation of some clear and unambiguous C# code into an arguably pointless and obscure LINQ expression doesnt teach anything about monads to C# programmers.

I mean, if we translate that LINQ expression back into C#, we end up with a bunch of nested foreach loops, where the TryFind() method returns collections containing 0 or 1 items. What the hell does that have to do with monads?

# re: Much Ado About Monads – Maybe Edition

Tuesday, February 10, 2009 1:35 PM by Jason

Thanks for this post, Matt.  I've found learning all this new (to me) material challenging, and appreciate your efforts to "catalog" some of this theory.. (pun.. eh? eh??)

# re: Much Ado About Monads – Maybe Edition

Monday, February 16, 2009 4:50 PM by podwysocki

@Jason,

Thanks!  Still more to come in this series.

Matt

# re: Much Ado About Monads – Maybe Edition

Friday, January 25, 2013 1:27 PM by Meredith

Excellent blog. That's exactly what I was looking for.

# re: Much Ado About Monads – Maybe Edition

Sunday, March 3, 2013 6:51 AM by Cameron

What i don't understood is actually how you are not really much more neatly-appreciated than you might be now. You are so intelligent. You know thus considerably when it comes to this subject, produced me personally imagine it from a lot of varied angles. Its like men and women aren't involved until

it is one thing to accomplish with Woman gaga! Your individual stuffs excellent.

Always deal with it up!

# re: Much Ado About Monads – Maybe Edition

Friday, March 8, 2013 3:32 AM by King

I am sure this paragraph has touched all the internet people,

its really really fastidious post on building up new webpage.

# re: Much Ado About Monads – Maybe Edition

Friday, March 8, 2013 2:27 PM by Nagy

Hi there to every body, it's my first pay a visit of this weblog; this web site contains awesome and truly excellent stuff in support of visitors.

# re: Much Ado About Monads – Maybe Edition

Saturday, March 9, 2013 11:21 AM by John

Hello! I just wanted to ask if you ever have any issues with hackers?

My last blog (wordpress) was hacked and I ended up losing months of hard work due to no backup.

Do you have any solutions to prevent hackers?

# re: Much Ado About Monads – Maybe Edition

Thursday, April 4, 2013 8:02 AM by qrlXMDtJutJhyjMNYj

txAp5l Im obliged for the article.Really looking forward to read more. Want more.