A couple of friends recently asked me … what is a Monad? I decided to use it as an excuse to join the many authors of monad tutorials. Below is my little explanation using F# for examples.
When one starts down the road of functional programming, an interesting conclusion about composition and sequence is always arrived at early.
As functions like
let f x = y
and
let g y = z
are created writing g ( f x ) always seems to come naturally. And it is obvious that in a strict language (like F#) f will be applied to x and g will be applied to the result creating an intuitive sequence of actions. Programmers today have very little trouble with this because of the familiar dot “.” notation.
new MyObject()
.GetSomething()
.ApplyToResult()
… etc
An exciting exploration in the young functional programmer results and they come to the conclusion that the ability to chain multiple functions in this fashion would be useful. Suddenly their functional code begins to take advantage of all of the functional bells and whistles while adding an imperative look.
To do this they need only define a composition operator (already defined in F#)
let (|>) x f = f(x)
so they can write sequences that look very much like the dot “.” notation above.
x
|> getSomething
|> applyToResult
Beautiful! Of course we haven’t broken any new ground yet. But the preceding discussion has led us to an interesting problem. This approach, in general, requires us to mold our types around our program. In order for “getSomething” to be applied it must both accept the type of “x” and result in the type in which “applyToResult” accepts. Lining these types up is perfectly acceptable for some small programs, but if we want to build up a larger object, or glue together programs that come from different architectures then we wind up writing code to massage the types – that forces us to work for the type system rather than the other way around.
Also, consider how the above code handles failure – it really doesn’t! If “getSomething” fails it must throw an exception, or the code to deal with failure must be in every single subsequent function in the chain. For a chain of 10 functions this creates an enormous amount of work – not to mention possible failure states. This is exactly how most software is written today – we rarely create a seperate module for failure (or other logic that must happen between the lines). Rather we expect it to be dealt with explicitly
Another way to go is to put the logic that handles what should happen between functions into its own function. Let’s call that function “bind”. The function “bind” should take a single value type (call it M) that encapsulates the data (of type ‘a) that we are working with. So bind takes as its first argument M<’a>.
What should it take as the second argument? How about a function that takes M<’a> and returns M<’a>? The problem with that approach is that the protected and encapsulated value inside of a should only be retrieved if we are in a good state, and its retrieval should be a seperate module – that is the point of the bind function. So let’s assume bind somehow gets the value of type ‘a out of M<’a>. Then the second argument would be a function that takes ‘a and returns M<’b> (where ‘b may or may not be the same type as ‘a).
So now we write code like …
bind M(x) (fun y ->
bind (getSomething y) (fun z ->
bind applyResult z))
Not very pretty is it? What if we make bind an operator?
let (>>=) = bind
Then we can write
M(x) >>= fun y ->
getSomething y >>= fun z ->
applyResult z
Still not too pretty. Ok, to solve this problem languages like F# just allow some clean syntax and compile down to what you see above.
Haskell uses a “do” notation to accomplish this, but we will focus on F# and its computation expressions/workflows in this post. So let’s create an example – in fact one of the most common examples when it comes to Monads (a little googling and you will find the example below several times over). We will have a computation that can fail at any step – but we don’t want to have to deal with its failure over and over. We would rather just have failure dealt with in the bind function, and everything else should be able to ignore it.
let option<'a> =
| Some of 'a
| None
Now that we have the bind function lets create our Maybe structure that F# will use to help us create cleaner syntax.
let bind v f = match v with | None -> () | Some(x) -> f x
type Maybe() =
member o.Bind(v,f) = bind v f
member o.Return(v) = Some(v)
In F# the type of monad/workflow must be explicitly declared. So the syntax F# uses includes the type of workflow you will be invoking, along with the program inside curly braces.
let maybe = Maybe()
let con() =
maybe {
let c = getDBConnection()
if validCon(c) then return! Some(c) else return! None}
The return! (with exclamation point) is just a convenient way for us to return the result of a maybe expression (rather than return the underlying value). The underlying value would have to be wrapped in an option type before we could return it – that is done easily enough with the normal return (no exclamation point) keyword.
Lets add some work to this program that really emphasizes the failure capture. We will add a “queryDB” function.
let queryDB c q =
maybe {
let v = queryDB q
if verify v then return! Some(v) else return! None}
let queryVal q =
maybe { let! c = con() // c is assured after this line
let! v = queryDB c q
return v }
Note that the code above does no obvious exception handling, or other failure management. It just has the “maybe” claim before the code block. That ensures the the “maybe” bind function is called at each “let!”. And the “return” function packages the value into an option type (as Some(x)). So while we use this cleaner syntax above, ultimately
let! c = con()
compiles to
maybe.Bind(con(),fun c ->
//rest of the program
Thanks to bind handling each of the composition steps, we don’t have to worry about failure in all of our computations anymore. Bind has offered us a great deal of modularity, we can finally seperate the concerns of failure from our line by line logic.
I have used these structures for image processing, asynchronous computing, IO (in Haskell), lists, failure handling (as above) and have found it to be a surprisingly prolific architectural approach to difficult problems. When you create a seperate module to handle the composition of different systems, much of the world of programming opens up to you. You can deliver solutions for complex systems that are easier to understand – chewing away at your software’s complexity.
We will be working through many other concepts in F# at our training session on 11/14 in Austin, Texas. If you are in the area you are welcome to sign up.
[Aside: Mathew Podwysocki has a couple of very interesting posts - including using the structure above for asynchronous computing in C#: End of Aside]
