Home > Uncategorized > Monads

Monads

I have been playing with monads (a.k.a. computation expressions or workflows in F#) a bit lately. From wikipedia we can learn, among other things, that:

“In functional programming, a monad is a kind of abstract data type constructor used to represent computations (instead of data in the domain model). Monads allow the programmer to chain actions together to build a pipeline, in which each action is decorated with additional processing rules provided by the monad. ”

Monads is indeed nothing new and Haskell programmers have been using them for years but I have not really taken the time to dig into the theory before. I should also add that this blog entry does not claim to be unique (or even creative) and all the material provided here are also available at many places. A couple of good links that I have been reading are:

I lift my hat of and say “thank you” to the great programmers behind.

Anyway, the simplest monad of them all is the the maybe monad. The maybe monad is useful when chaining function calls that may fail or return nothing. Take a deep breath, here is one possible F# definition:

type MaybeMonad() =

    member b.Return(x) = Some x

    member b.Bind(m, f) =

        match m with

        | None -> None

        | Some x -> f x

 

let maybe = MaybeMonad()

 

A sample usage may look like:

let failIfBig n = if n > 1000 then None else (Some n)

 

let safesum inp1 inp2 =

    maybe { let! n1 = failIfBig inp1

            let! n2 = failIfBig inp2

            let sum = n1 + n2

            return sum }

 

printf "%A\n" (safesum 10 20)

printf "%A\n" (safesum 10000 20)

 

The safesum function uses a special “workflow” syntax which is translated by the compiler to (something like):

let safesum’ inp1 inp2 =

    maybe.Bind(failIfBig inp1, fun n1 ->

        maybe.Bind(failIfBig inp2, fun n2 ->

            let sum = n1 + n2

            maybe.Return(sum)))

 

My next step was to grok the state monad. The state monad is useful for hiding a state parameter that is “threaded” through a computation. Take another deep breath – here comes a possible state monad definition (again using F# ofcourse):

type StateMonad() =

    member this.Return(a) = fun s -> a,s

    member this.Bind(m, f) = fun s0 ->

                                let a,s = m s0

                                let m’ = f a

                                m’ s

 

let state = StateMonad()

 

Along with the monad, it is common to provide the following helpers:

let getState = fun s -> s,s

let setState s = fun _ -> (),s

let execute m s0 = m s0 |> fst

 

A sample usage may look like this:

type BinTree<‘a> = Leaf of ‘a | Node of BinTree<‘a>*BinTree<‘a>

 

let rec labelTree t =

    state {

        match t with

        | Leaf x ->

            let! s = getState

            do! setState (s+1)

            return Leaf (x,s)

        | Node (l,r) ->

            let! l’ = labelTree l

            let! r’ = labelTree r

            return Node (l’,r’)

    }

 

 

let sampleTree =

    Node(

        Node(Leaf "a", Leaf "b"),

        Leaf "c")

 

execute (labelTree sampleTree) 0 |> printf "%A\n"

 

Using the state monad is, as shown above, not that hard. Understanding the magic behind requires more thought.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: