As part of my talk at the Richmond Code Camp earlier in October, I had the opportunity to talk about how to implement functional aspects in C# 3.0. This talk revolved around such concepts as from mutable to immutable, from inheritance to functional composition, and the mind shift that is required. Part of this discussion involved very briefly a talk about monads. It's a very misunderstood part of computer science and one of the most powerful concepts to learn. Much like continuation passing style, this style is often maligned as a result. But, let's work to change that.
What Is a Monad?
Monads come to us originally from category theory. When monads applied to functional programming, they simply are a construction, given an underlying type system, embeds a corresponding monadic type system. Simply put, the values you have become amplified values that are to be interpreted by the matching monadic type.
The formulation of a monad comes in three parts:
- A type construction that defines for every underlying type, how to obtain a corresponding monadic type. If the given type in F# is 'a, then the corresponding monadic type for an Identity monad would be I<'a>. I'll cover more of what that means below.
- A unit function that maps the underlying type to a value in the corresponding monadic type. In F# parlance, this maps to a Return function.
- A binding operation of polymorphic type, in F# parlance, (I<'a>) => ('a => I<'b>) => (I<'b>). This maps to a Bind function given your monad builder. If you look carefully at the signature of this, you might also note that the LINQ SelectMany follows this syntax. Gee, what could that mean? The bind operation follows four steps:
- The monadic structure exposes the underlying value of type 'a.
- The given function is applied to the underlying value to obtain values of type I<'b>
- The monadic structure exposes the underlying value of type 'b.
- The monadic structure is reassembled over the results, given a single value of type I<'b>
Simply put, a monad, unlike your normal function results, stores function results and side-effect representations. This allows side effects to be propagated through the return values of functions without breaking the pure functional model. This is what makes it so powerful that it is a way to manage side effects. Given a pure language such as Haskell, this is the way that any side effecting operation should be done. Granted, there are impure ways of doing IO, but let's not go there.
There are some good sources of information on what monads are, including some great stuff from Brian Beckman:
Some examples of monads that are used frequently are such things as the maybe monad, identity monad, IO, collections and so on. Let's move onto implementing some of these monads in .NET, whether it be F# or even C#.
Implementing in .NET
To implement the above mentioned monads, we'll take examples in both F# and C# to see that both can do the job. Although I'll admit my preference for F#, C# can monads quite nicely using LINQ syntax. But that sometimes means that the from and select keywords might be confusing. But what people might not realize is that you are not limited to IEnumerable<T> inside LINQ. Instead, you could have any backing type you want. For example, I could have the identity type, maybe type, async type and so on. We'll cover each one of those in detail in the following sections.
Anyhow, let's get started with the identity monad.
The Identity Monad
The easiest monad to understand is the identity monad. This attaches no information to the underlying value, and instead only returns and transforms it.
Implementing in F#
To implement in F#, we need to remember what's required for any monad builder. That is the Bind, Return, Delay and Let functions. Let's define our builder first with the given functions.
#light
type I<'a> = 'a
let bindI i f = f i
let resultI i = i
let delayI f = f()
type IdentityBuilder() =
member x.Bind(i, f) = bindI i f
member x.Return(i) = resultI i
member x.Delay(f) = delayI f
member x.Let(i, f) = bindI (resultI i) f
Now that our builder is defined, F# has a special way of representing monads in that you wrap them in curly braces with the given instance name of the monad builder. In this case, I'll call it ident.
let ident = IdentityBuilder()
let iValue = ident {
let! x = 5
let! y = 42
return! x + y
}
printfn "%i" iValue
The above code allows me to define x and y and add them together. The end result ends up being 47. This looks pretty simple using this syntax, although this is what it ends up being behind the scenes:
let iValue = ident.Delay(fun () ->
ident.Bind(5, fun x ->
ident.Bind(42, fun y ->
ident.Return(x + y))))
As you can see, the syntax is much more simplified with the syntactic sugar that they give us. This almost looks like LINQ in a way.
Implementing in C# 3.0
Now, what about C#? What can we do there? Actually, the answer is, that it's quite simple. If you notice one thing about LINQ is the signature of the SelectMany method. Let's look at the definition on the Enumerable class.
public static IEnumerable<U> SelectMany<T, U>(
this IEnumerable<T> s,
Func<T, IEnumerable<U>> f)
And if you look at the bind syntax that we used in our F# example, it's exactly the same signature. That should tell us something that LINQ expressions can indeed be monads. Now, let's implement the identity monad by first identifying the class and then the extension methods that make this work.
public class Identity<T>
{
public Identity(T value) { Value = value; }
public T Value { get; private set; }
}
public static class IdentityExtensions
{
public static Identity<T> ToIdentity<T>(this T value)
{
return new Identity<T>(value);
}
public static Identity<U> SelectMany<T, U>(
this Identity<T> id,
Func<T, Identity<U>> k)
{
return k(id.Value);
}
public static Identity<V> SelectMany<T, U, V>(
this Identity<T> id,
Func<T, Identity<U>> k,
Func<T, U, V> s)
{
return id.SelectMany(x => k(x).SelectMany(y => s(x, y).ToIdentity()));
}
}
When we implement things for LINQ, we must be cognizant for the need of two SelectMany methods for various performance reasons to allow us to combine values. Now that we've defined these methods, we can now use LINQ expressions to express our identity monad.
var identResult = from x in 5.ToIdentity()
from y in 42.ToIdentity()
select x + y;
Console.WriteLine(identResult.Value);
As above the answer comes out to 47. Let's move onto the maybe monad.
The Maybe Monad
The maybe monad is another popular monad type. A maybe monad is very similar to the identity, yet a value may be missing. In F# parlance, this translates to the Option<'a> type. Let's go ahead and implement this in F# using our given option type.
Implementing in F#
Implementing the maybe monad is very similar to the identity monad. The only difference being is the to differentiate between some value and no value specified. We will determine that through pattern matching, as always.
#light
type M<'a> = option<'a>
let bindM d f =
match d with
| None -> None
| Some(v) -> f v
let resultM v = Some(v)
let delayM f = f()
type MaybeBuilder() =
member x.Bind(v, d) = bindM v d
member x.Return(v) = resultM v
member x.Delay(f) = delayM f
member x.Let(v, f) = bindM (resultM v) f
Once defined, we can now use our MaybeBuilder to define a simple use of our maybe monad. Let's make sure we use None to denote that we are missing a value.
let maybe = MaybeBuilder()
let mValue = maybe {
let! x = Some(5)
let! y = None
return x + y
}
let option_to_string = function
| None -> "Undefined"
| Some v -> v.ToString()
printfn "%s" (mValue |> option_to_string)
The result of course is "Undefined" because our y value is the None option type. But, how might this work in C#?
Implementing in C# 3.0
We can reuse a lot of our ideas from implementing this via extension methods. I will go ahead and use the Option type that I've defined in my Functional C# project on MSDN Code Gallery. From there, we can implement our SelectMany operations.
public static class MaybeExtensions
{
public static Option<T> ToMaybe<T>(this T value)
{
return Option<T>.Some(value);
}
public static Option<U> SelectMany<T, U>(
this Option<T> m,
Func<T, Option<U>> k)
{
return !m.IsNone ? Option<U>.None : k(m.Value);
}
public static Option<V> SelectMany<T, U, V>(
this Option<T> m,
Func<T, Option<U>> k,
Func<T, U, V> s)
{
return m.SelectMany(x => k(x).SelectMany(y => s(x, y).ToMaybe()));
}
}
Now that we defined our binding operations, we can move onto actually using the maybe monad. Let's use the template that we defined up above for our identity monad and craft it to use our maybes.
var maybeResult = from x in 5.ToMaybe()
from y in Option<int>.None
select x + y;
Console.WriteLine(
maybeResult.IsSome ? maybeResult.Value.ToString() : "Undefined");
Once again, our result will be undefined as our y value has no real value at all. Clear so far? Let's move onto the List Monad.
The Collection Monad
The collection monad is another important monad type. This monad is the heart and soul of LINQ and the way we use it to compute our lazily evaluated lists. This monad strikes home as one of the most important to .NET developers. Using LINQ to SQL, XML and such uses collections of various sorts to transform the data into other forms.
Implementing in F#
As before, we need to define our basic bind, let, return and delay functions in order for the monad to work in F#. Let's define the list monad to use seq<'a>. This way, I can lazily evaluate my results and yield them when I need to. For the bind and result statements, I'm using a sequence expression to yield the appropriate values.
#light
let bindL l f =
seq{for x in l do
for y in f x do
yield y}
let resultL l = seq{ yield l }
let delayL f = f()
type SeqBuilder() =
member x.Bind(l, f) = bindL l f
member x.Return(l) = resultL l
member x.Delay(f) = delayL f
member x.Let(l, f) = bindL (resultL l) f
Now that we've defined our monad builder, let's implement this to add the values from each collection to each other.
let seqMonad = new SeqBuilder()
let sValue = seqMonad {
let! x = {1..3}
let! y = {4..6}
return x + y
}
sValue |> Seq.iter(fun x -> printfn "%i" x)
Our results will be the addition of each number in each list to each other. So, in turn, I will get 9 numbers in total with a value of 5 6 7 6 7 8 7 8 9.
Implementing in C# 3.0
To view the bind methods, simply open the Enumerable class to view the SelectMany implementations. This will get us started in looking at a C# equivalent to the list monad we did above. A simple representation might look like this.
var sValues = from x in Enumerable.Range(1, 3)
from y in Enumerable.Range(4, 3)
select x + y;
foreach (var sValue in sValues) Console.WriteLine(sValue);
And we now realize the answers between the two are exactly the same. No special magic required for list monads.
The Asynchronous Monad
One of the most often used monads in F# is the asynchronous computation expression. This allows us to use non-blocking calls to download resources, whether it be files, web request, WCF calls and so on. This is where monads become really useful for .NET developers who want to explore a little outside the box in ways of thinking about monads.
Implementing in F#
We get the asynchronous computation expressions out of the box with F#. This allows us to easily create asynchronous computation expressions which I talked about earlier here. But, let's look at one example of downloading the HTML from various web sites in parallel with non-blocking calls. What might that look like?
#light
open System.IO
open System.Net
open Microsoft.FSharp.Control
open Microsoft.FSharp.Control.CommonExtensions
let get_html_async (url:string) =
async {
let request = WebRequest.Create(url)
let! response = request.AsyncGetResponse()
let stream = response.GetResponseStream()
let reader = new StreamReader(stream)
let! text = reader.AsyncReadToEnd()
return text
}
let urls = ["http://live.com"; "http://google.com"; "http://codebetter.com"]
let textResults =
Async.Run(Async.Parallel [for url in urls -> get_html_async url])
textResults |> Seq.iter(fun textResult -> printfn "%s" textResult)
As you can see, we're creating a request, getting the response, creating a reader, and reading all the way to the end asynchronously. As you may note, there is a difference between let! and let. The let! uses the Bind method whereas the let uses the Let method of AsyncBuilder. What I'm able to do here is take three websites, and download their HTML and display within a short amount of time. Imagine if I had to write that using IAsyncResult classes and such. That wouldn't be ideal! But, can C# partake in this?
Implementing in C# 3.0
The question I asked is that can we take advantage of the F# asynchronous computation expressions in C#? The answer, surprisingly is YES! I had the opportunity to talk to F# developer, Brian McNamara, on this very subject. Back in May, he posted a quick example of using the F# libraries from C#. There is a bit of work required to do this, but it pays off handily. I'll cover the exact details in my next post of how to do it. But, in the mean time, imagine if we could download HTML from three websites simultaneously using LINQ? Here's what the code that does exactly that looks like.
Func<string, Async<string>> get_html_async = url =>
from _ in AsyncExtensions.StartWorkflow
from request in WebExtensions.AsyncCreateWebRequest(url)
from response in request.AsyncGetResponse()
let reader = new StreamReader(response.GetResponseStream())
from urlText in reader.AsyncReadToEnd()
select urlText;
var urls = new[] { "http://live.com/", "http://www.google.com/", "http://codebetter.com/" };
var urlTexts = Async.Run(
Async.Parallel(from url in urls select get_html_async(url)), Option<int>.None, Option<bool>.None);
Array.ForEach(urlTexts, Console.WriteLine);
How simple is that? Well, we have to put some backing to some of these methods in order to make them asynchronous, and I will cover exactly what that is in the next post.
Wrapping it Up
What about such things as the IO monad? Well, that's more of a language construct that is enforced by the compiler. I would like to see something similar to this in F# going forward, so that we could better manage our side effects. Using such technologies as Spec# to statically verify the behavior is important. But, once again, that's another post.
I hope I helped to alleviate some of the confusion around monads. More importantly, I hope you know more of how and when to use them. In the next post, I'll follow up with the actual implementation of the asynchronous computation expressions in C# 3.0. Giving us the ability to have parity with F# is really powerful and attests to the power of LINQ (and monads of course). Stay tuned!