The Maybe Monad in F#

When learning something new I like to focus on the things that I can’t do with my current programming skill set.  The first time I skimmed through Expert F# I realized there’s a whole lot of skill set that I don’t have.  Of particular interest was the concept of monads/computations/workflows.

I can’t say I like the use of three names for this concept.  Don Syme explains some reasoning for the use of workflows over monads.  I have to disagree with the reasoning, redefining a term the community already uses for a concept only makes it more confusing and inaccessible.  It reminds me of the VB discussion over whether refactoring is too technical for the puny minds of Morts.

If you google monads then you get a bunch of relevant hits that you can use to learn the concept.  If you google workflows you get a dead end.  I like the word monad, hopefully I can make the word monad “friendly” to other programmers the old fashioned way, by explaining them.

The Maybe Monad

My first attempt at writing a monad was based on this Wikipedia article.  In this implementation the Maybe monad is simply a typedef for an option type. 

 

type Maybe<’a> = option<’a>

 

let succeed x = Some(x)

let fail = None

let bind p rest =

    match p with

        | None -> fail

        | Some r -> rest r

let delay f = f()

 

type MaybeBuilder() =

    member b.Return(x)  = succeed x

    member b.Bind(p, rest) = bind p rest

    member b.Delay(f)   = delay f

    member b.Let(p,rest) : Maybe<’a> = rest p

   

let maybe = MaybeBuilder()

 

I had read quite a bit on monads, but until I actually wrote one the first time I can’t say I truly understood them. Using intellisense to examine the type information in invaluable to understanding the scaffolding.  When I first read Expert F# I really struggled with the type explanations, now I can’t do without them.  Let’s examine out binding operation first.

 

//val bind : ‘a option -> (’a -> ‘b option) -> ‘b option

let bind p rest =

    match p with

        | None -> fail

        | Some r -> rest r

 

The problem with the inferred types is option is used instead of our typedef for option.  Let’s make this more explicit.

 

// val bind : Maybe<’a> -> (’a -> Maybe<’b>) -> Maybe<’b>     

let bind (p : Maybe<’a>) (rest : ‘a -> Maybe<’b>) : Maybe<’b> =

    match p with

        | None -> fail

        | Some r -> rest r

 

 So our binding operation

·         accepts a maybe monad  Maybe<’a>

·         and a function that transforms the underlying type of the maybe monad ‘a

·         into some other underlying type ‘b

·         which gets wrapped by another maybe monad  Maybe<’b>

·         then returned by our bind function

The body of our bind function pierces the monad to expose the underlying type then either fails the operation or passes it on the next function in the chain.

Using our Maybe Monad

Here’s some example code that uses our Maybe monad.

 

let failIfBig n = maybe {if n > 1000 then return! fail else return n}

 

let safesum (inp1,inp2) =

    maybe { let! n1 = failIfBig inp1

            let! n2 = failIfBig inp2

            let sum = n1 + n2

            return sum }

 

It becomes easier to see how our Bind operation works when we rewrite the above code without the “syntactic sugaring”.

           

let desugar (inp1,inp2) =

    maybe.Bind(failIfBig inp1, (fun n1 ->

        maybe.Bind(failIfBig inp2, (fun n2 ->

            maybe.Let(n1 + n2, (fun sum ->

                maybe.Return(sum)))))))

 

Now let’s break out our function into steps.

 

let step2 inp2 = (fun n1 ->

        maybe.Bind(failIfBig inp2, (fun n2 ->

            maybe.Let(n1 + n2, (fun sum ->

                maybe.Return(sum))))))

               

let desugar_in_steps (inp1,inp2) =

    maybe.Bind(failIfBig inp1, step2 inp2)

 

If we look back at what our binding operation does to pierce the monad

 

match p with

        | None -> fail

        | Some r -> rest r

 

it should be obvious that we will not continue on to step 2 if we fail on our initial bind.  Our binding operation has inserted a check at each step that prevents the computation from proceeding if it fails.  The ability to insert functionality at each step is what monads are all about.

 

Next time we’ll take a look at several possible type definitions for the monad and analyze the pros and cons of each.

Full source

Here’s the full source code for reference.

 

#light

 

type Maybe<’a> = option<’a>

 

let succeed x = Some(x)

let fail = None

let bind p rest =

    match p with

        | None -> fail

        | Some r -> rest r

let delay f = f()

 

type MaybeBuilder() =

    member b.Return(x)  = succeed x

    member b.Bind(p, rest) = bind p rest

    member b.Delay(f)   = delay f

    member b.Let(p,rest) : Maybe<’a> = rest p

   

let maybe = MaybeBuilder()

 

let failIfBig n = maybe {if n > 1000 then return! fail else return n}

 

let safesum (inp1,inp2) =

    maybe { let! n1 = failIfBig inp1

            let! n2 = failIfBig inp2

            let sum = n1 + n2

            return sum }

           

let result1 = safesum (999,1000)

printfn “%A” result1

let result2 = safesum (1000,1001)

printfn “%A” result2

System.Console.ReadLine()