Wednesday, May 13, 2009

Monads pt. 2

In my previous post I derived the Maybe monad through a sequence of refactorings. In this post I will delve into another practical example that builds on the previous code we wrote. Refresh yourself here.


At the conclusion of my previous post I mentioned a couple impurities in our implementation:

1) The Bind function named _IfSuccessful_ resides in the Maybe class when in fact it should be separate from the monad wrapper.

2) We are missing the Unit function which elevates the base type to the monadic type i.e. from the string "john" to the Maybe object _maybejohn_.


I will define the Bind and Unit functions as extension methods:

    8 public static class MaybeExtensions

    9 {

   10     public static Maybe<Out> IfSuccessful<In, Out>(this Maybe<In> instance, Func<Maybe<In>, Maybe<Out>> f)

   11     {

   12         if (instance != null)

   13         {

   14             return f(instance);

   15         }

   16         return null;

   17     }

   18 

   19 

   20 

   21     public static Maybe<T> Unit<T>(this T s)

   22     {

   23         if (s != null)

   24         {

   25             var maybe = new Maybe<T>();

   26             maybe.Value = s;

   27             return maybe;

   28         }

   29         return null;

   30     }

   31 }



A couple things of note:

the _IfSuccessful_ method from my previous post took in a Func<Maybe<T>, Maybe<T>> as an arg. The new version now takes in two args, the first is by virtue of an extension method is the caller of the extension method. The second arg has been modified from original Func<Maybe<T>, Maybe<T>> to be Func<Maybe<In>, Maybe<Out>>. This implies the function has the ability to output a Maybe object wrapping a different underlying type from the input Maybe object. Basically, the original implementation was contrived and overly simplified; time for the training wheels to come off. Another change to the _IfSuccessful_ method is foregoing the _IsNothing_ boolean and simply testing for _null_ instead. This doesn't change the overall behavior; _null_ is just a simpler, more generic thing to check for than a boolean flag.

The Unit() extension method takes the caller and promotes it to its Maybe type (if the caller is not _null_).

And here's the new Maybe class after cleaning it out:

    8     public class Maybe<T>

    9     {

   10         public T Value; 

   11     }




We are ready to tackle our imaginary business problem:

A large company has a policy that provides education grants for employee's dependents. The catch is that the employee is qualified to receive this money if the dependent's report card shows an 'A' average. This business rule can be explicitly written as:

  118             Func<Employee, ReportCard, Employee> TestAndApplyEducationGrant =

  119                 (employee, dependentReportCard) =>

  120                 {

  121                     //if the dependent's grade is an A

  122                     if (dependentReportCard.Grade == "a")

  123                     {

  124                         //give employee the grant

  125                         employee.Grant = new Grant();

  126                         return employee;

  127                     }

  128                     else

  129                     {

  130                         //not qualified for the grant

  131                         return null;

  132                     }                   

  133                 };



Here's the supporting story:

  137         var Joe = new Company().FindEmployee("joe");

  138         var IsSuccessful = false;

  139 

  140         if (Joe != null)

  141         {

  142             var joeDependent = Joe.GetDependent();

  143 

  144             if (joeDependent != null)

  145             {

  146                 var dependentSchool = joeDependent.GetSchool();

  147 

  148                 if (dependentSchool != null)

  149                 {

  150                     var reportCard = dependentSchool.FindReportCard(joeDependent.Name);

  151 

  152                     //here is the business rule

  153                     var result = TestAndApplyEducationGrant(Joe, reportCard);

  154 

  155                     if (result != null)

  156                     {

  157                         //save the result somewhere and inform us of failure

  158                         IsSuccessful = new DB().Persist(result);

  159                     }

  160                 }

  161             }

  162         }



The nested _if_ statements are necessary to traverse through the object graph, checking for a blocking null.

Here is the code using the monad:

  169 var result =

  170     maybeJoe.IfSuccessful(employee => employee.Value.GetDependent().Unit())

  171                      .IfSuccessful(dependent => dependent.Value.GetSchool().Unit())

  172                      .IfSuccessful(school => school.Value.FindReportCard(maybeJoe.Value.GetDependent().Name).Unit())

  173                      .IfSuccessful(reportCard => TestAndApplyEducationGrant(maybeJoe.Value, reportCard.Value).Unit())

  174                      .IfSuccessful(employee => new DB().Persist(employee).Unit());



Notice the call to Unit() at the tail of each method call. Remember Unit() wraps the raw object back into the Maybe type so that it can be passed on to the next Bind function. Taking a step back to take a look at the larger picture, we can see that the .Value method accesses the base type - or "unboxes" it, work is then performed and the result is "boxed" up again by the Unit() call and passed on to the next step.

We have to be mindful of designing the object methods such that it returns _null_ if it fails to retrieve/perform its work. That way, _result_ will be non-null if the whole workflow succeeds, null otherwise.

The monad shortens the code considerably, improving its fluency as well.

Sunday, May 3, 2009

Monads in C#

Ready to learn monads?

Here is a tutorial for the rest of us. Let us begin.

I'm dreaming of some code, a function that takes a person's name and returns true if he can be found in the phone book, Facebook, and MySpace; it returns false otherwise. Our first write of the code might look like this:

   18             if (IsInPhoneBook("John") && IsInFacebook("John") && IsInMySpace("John"))

   19             {

   20                 return true;

   21             }

   22             else

   23             {

   24                 return false;

   25             }



We can wrap it in a method of this signature somewhere:

27 public Boolean PersonCanBeFound(String name)



However, with this implementation we are effectively locked into the expression that checks for John in all three medias. Suppose if we wish to check against only Facebook and MySpace, then we are outta luck. So, let's explore another behavior:

   29 var result = MaybeJohn.IsInPhoneBook().IsInFacebook().IsInMySpace();



Fluent interface allows us to chain the calls. MaybeJohn is of type Maybe such that:

   28 Maybe<String> MaybeJohn = new Maybe<String>() { Value = "John"};

   29 var result = MaybeJohn.IsInPhoneBook().IsInFacebook().IsInMySpace();



where we can use it like so:

   30 if (result.IsNothing)

   31 {

   32     //prints "John cannot be found!"

   33     Console.WriteLine("{0} cannot be found!", MaybeJohn.Value);

   34 }

   35 else

   36 {

   37     //prints "John found!"

   38     Console.WriteLine("{0} found!", MaybeJohn.Value);

   39 }



The IsNothing attribute stores our result: It stores _True_ if John can be found in the phonebook and Facebook and MySpace. Else it holds _False_. Simple enough. Let's code up the Maybe class. Here's our first stab:

   74 public class Maybe<T>

   75     {

   76         public T Value;

   77         public Boolean IsNothing = false;

   78 

   79         public Maybe<T> IsInFaceBook()

   80         {

   81             //Only do work if we don't have an answer yet

   82             if (!this.IsNothing)

   83             {

   84                 //let's do some work here through some imaginary service

   85                 Boolean isFound = new SomeService().Lookup("phonebook", Value);

   86 

   87                 //set the property

   88                 this.IsNothing = !isFound;

   89                 return this;

   90             }

   91             return this;

   92         }

   93 

   94         public Maybe<T> IsInPhoneBook()

   95         {

   96             //Only do work if we don't have an answer yet 

   97             if (!this.IsNothing)

   98             {

   99                 //let's do some work here through some imaginary service

  100                 Boolean isFound = new SomeService().Lookup("facebook", Value);

  101 

  102                 //set the property

  103                 this.IsNothing = !isFound;

  104                 return this;

  105             }

  106             return this;

  107         }

  108 

  109         public Maybe<T> IsInMySpace()

  110         {

  111             //Only do work if we don't have an answer yet

  112             if (!this.IsNothing)

  113             {

  114                 //let's do some work here through some imaginary service

  115                 Boolean isFound = new SomeService().Lookup("myspace", Value);

  116 

  117                 //set the property

  118                 this.IsNothing = !isFound;

  119                 return this;

  120             }

  121             return this;

  122         }

  123     }



The code works, but it smells of:
1) duplication. All the methods are identical except for the SomeService.Lookup call.
2) tight coupling. This is more subtle, but it's not the best idea to imbed the service calls (i.e. database/webservice call) into this class. It tightly couples the logic to use a service call when service calling is just a periphery issue. I'd rather be able pass in an implementation that may or may not use SomeService.Lookup.

Let's extract the duplicate code inside the _if_ block into an independent function outside of the Maybe class. The function should take in a couple args since we no longer have the luxury of the _this_ pointer. Here it is written as a first-class function:

   41 Func<Maybe<String>, String, Maybe<String>> CheckMedia =

   42     (maybe, media) =>

   43         {

   44             //some imaginary service

   45             Boolean isFound = new SomeService().Lookup(media, maybe.Value);

   46 

   47             maybe.IsNothing = !isFound;

   48             return maybe;     

   49         };



To use the CheckMedia function, we pass it as an arg to the methods in the Maybe class:

   52 var result = MaybeJohn.IsInPhoneBook(CheckMedia)

   53                       .IsInFacebook(CheckMedia)

   54                       .IsInMySpace(CheckMedia);



and we make some changes to the Maybe class methods to accept the first-class function and to execute it:

   37     public class Maybe<T>

   38     {

   39         public T Value;

   40         public Boolean IsNothing = false;

   41 

   42         public Maybe<T> IsInFaceBook(Func<Maybe<T>, String, Maybe<T>> mediaCheck)

   43         {

   44             if (!this.IsNothing)

   45             {

   46                 return mediaCheck(this, "phonebook");

   47             }

   48             return this;

   49         }

   50 

   51         public Maybe<T> IsInPhoneBook(Func<Maybe<T>, String, Maybe<T>> mediaCheck)

   52         {

   53             if (!this.IsNothing)

   54             {

   55                 return mediaCheck(this, "facebook");

   56             }

   57             return this;

   58         }

   59 

   60         public Maybe<T> IsInMySpace(Func<Maybe<T>, String, Maybe<T>> mediaCheck)

   61         {

   62             if (!this.IsNothing)

   63             {

   64                 return mediaCheck(this, "myspace");

   65             }

   66             return this;

   67         }

   68     }



It works, and a lot less code!

We can do better still.

If we were to extend functionality and add a new media to check, say Twitter, we'd have to crack open the Maybe class and add another method named IsInTwitter.

Maintenance headache.
Let's only have one method in the Maybe class such that we can achieve something like:

   56 var result =

   57     MaybeJohn.IfFound(/*...pass in some function to do CheckMedia for John in facebook...*/)

   58              .IfFound(/*...pass in some function to do CheckMedia for John in myspace...*/)

   59              .IfFound(/*...pass in some function to do CheckMedia for John in twitter...*/);



The IfFound method takes in a function that transitions MaybeJohn to the next state as input for the following IfFound call. The function takes a Maybe, does work (CheckMedia) on it, and spits out the Maybe. Here we have it:

   60 var result = MaybeJohn.IfFound(john => CheckMedia(john, "facebook"))

   61                       .IfFound(john => CheckMedia(john, "myspace"))

   62                       .IfFound(john => CheckMedia(john, "twitter"));



The function takes advantage of lambda syntax. Next we make the changes for the Maybe class. The IfFound method takes in a first-class function and executes it:

   22     public class Maybe<T>

   23     {

   24         public T Value;

   25         public Boolean IsNothing = false;

   26 

   27         public Maybe<T> IfFound(Func<Maybe<T>, Maybe<T>> f)

   28         {

   29             if (!this.IsNothing)

   30             {

   31                 return f(this);

   32             }

   33             return this;

   34         }

   35     }



Boom that's it.

Wait. Where's the monad?

The concepts are all here. In functionese, the IsFound method is the Bind operator and in functionworld it is defined independently of any class. There is another function called Unit which we don't have here. Unit is simply a function that wraps the Maybe object around the string "John" to create MaybeJohn; We don't have this, we just new'ed one up. The term _monad_ refers to the Maybe class which is the container/wrapper. We have created the Maybe monad, and as they say "it's the simplest one of all."

In the next post I will show a practical reuse of this Maybe monad we've created.

new blog

I am not trying to defend a State School Education. I just think it is woefully inadequate.

yours truly,
JH