Rash thoughts about .NET, C#, F# and Dynamics NAV.


"Every solution will only lead to new problems."

Friday, 23. October 2009


Using monads in F# – Part I: The State Monad

Filed under: F# — Steffen Forkmann at 10:10 Uhr

Currently I’m trying to implement some of the standard monads in F#. If you want to read about the theory behind monads and their implementation (in Haskell) it’s a good start to look into “All about Monads” on haskell.org.

In this blog post series I don’t care about mathematical details. Instead I will try to show how monads can help to simplify our code.

Motivation

We have a generic binary tree with some test data:

type Tree<‘a> =

| Leaf of ‘a

| Branch of Tree<‘a> * Tree<‘a> 

 

let tree =

  Branch(

    Leaf "Max",

    Branch(

      Leaf "Bernd",

      Branch(

        Branch(

          Leaf "Holger",

          Leaf "Ralf"),

        Branch(

          Leaf "Kerstin",

          Leaf "Steffen"))))

If we want to print this tree we can use the following recursive function:

/// prints a binary tree

let printTree t =

  let rec print t level  =

    let indent = new String(‘ ‘, level * 2)

    match t with

    | Leaf l -> printfn "%sLeaf: %A" indent l

    | Branch (left,right) ->

        printfn "%sBranch:" indent

        print left (level+1)

        print right (level+1)

  print t 0

 

printfn "Unlabeled:"

printTree tree 

And what we get is something like this:

Unlabeled:

Branch:

  Leaf: "Max"

  Branch:

    Leaf: "Bernd"

    Branch:

      Branch:

        Leaf: "Holger"

        Leaf: "Ralf"

      Branch:

        Leaf: "Kerstin"

        Leaf: "Steffen"

Labeling the tree with mutable state

Now we want to give every tree a unique label. This can be easily done by another recursive function:

let mutable label = -1

let rec labelTreeMS t =

  match t with

  | Leaf l ->

      label <- label + 1 // changing the state

      Leaf(l,label) 

  | Branch(oldL,oldR) ->

      let newL = labelTreeMS oldL

      let newR = labelTreeMS oldR

      Branch(newL,newR)        

 

let treeMS = labelTreeMS tree

printfn "Labeled (with global mutable state):"

printTree treeMS     

And the output would look like this:

Labeled (with global mutable state):

Branch:

  Leaf: ("Max", 0)

  Branch:

    Leaf: ("Bernd", 1)

    Branch:

      Branch:

        Leaf: ("Holger", 2)

        Leaf: ("Ralf", 3)

      Branch:

        Leaf: ("Kerstin", 4)

        Leaf: ("Steffen", 5)

The only problem with labelTreeMS is that it uses global state, which is very bad because we can’t be sure if the mutable label variable is changed (from maybe another thread) or not.

Labeling the tree without global state

If we want to remove this side effect, we can pass the state directly into the function:

// non-monadic version

// passing the state around explicitly

let rec labelTreeNM t s =

  match t with

  | Leaf l -> s+1,Leaf(l,s)  // changing the state

  | Branch(oldL,oldR) ->

      let stateL,newL =

        labelTreeNM oldL s

      let stateR,newR =

        labelTreeNM oldR stateL  // passing the state around

      stateR,Branch(newL,newR)              

 

let _,treeNM = labelTreeNM tree 0

printfn "Labeled (non-monadic):"

printTree treeNM

Labeling the tree by using the State Monad

With the help of the State Monad we get a very similar function:

/// labels a tree by using the state monad

/// (uses F#’s sugared syntax)

let rec labelTree t = state {

   match t with

   | Leaf l ->

       let! s = getState

       do! setState (s+1)  // changing the state

       return Leaf(l,s)

   | Branch(oldL,oldR) ->

      let! newL = labelTree oldL

      let! newR = labelTree oldR

      return Branch(newL,newR)}

 

 

printfn "Labeled (monadic):"

let treeM = Execute (labelTree tree) 0

printTree treeM

Thanks to the F# sugared syntax this labelTree and labelTreeMS are visually nearly the same. Every time we are dealing with state we use the exclamation mark. There is only one point (in the Leaf case) where have to use (and change) the state.

The nice thing is, that we can write the function like the first version, but we don’t have to perform the side effect on the shared state.

If we want to use the de-sugared version we have to write it like this:

/// labels a tree and uses de-sugared syntax

/// (implementation looks different to labelTreeNM)

let rec labelTreeDesugared t =

   match t with

   | Leaf l -> (fun s -> Leaf(l,s),(s+1))

   | Branch(oldL,oldR) ->

       labelTreeDesugared oldL >>=

        (fun newL ->

           labelTreeDesugared oldR >>=

             (fun newR ->

                 Branch(newL,newR) |> returnS))   

State monad implementation

In order to use the state monad, of course we have to implement it first. Here is my version, which allows to use the de-sugared and sugared version:

module StateMonad

 

let (>>=) x f =

   (fun s0 ->

      let a,s = x s0

      f a s)      

 

let returnS a = (fun s -> a, s)

 

type StateBuilder() =

  member m.Bind(x, f) = x >>= f

  member m.Return a = returnS a

 

let state = new StateBuilder()

 

let getState = (fun s -> s, s)

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

let Execute m s = m s |> fst

 

If you want to learn more about the State Monad I recommend watching Brian Beckman’s Channel 9 video “The Zen of Stateless State – The State Monad".

Tags: , ,

3 Comments »

  1. let rec labelTreeMS t = match t with
    Why not
    let rec labelTreeMS = function
    ?

    Comment by guest — Sunday, 25. October 2009 um 12:08 Uhr

  2. Hi guest,

    there is no special reason for the named parameter. ;-)

    Regards,
    Steffen

    Comment by Steffen Forkmann — Sunday, 25. October 2009 um 13:01 Uhr

  3. Hi

    Thanks for writing this. I’m learning about monads. Was wondering why you defined returnS like you did instead of like this:

    > let returnS a b = a,b;;

    val returnS : ‘a -> ‘b -> ‘a * ‘b

    As far as I can tell they are the same?

    Comment by sashan — Thursday, 26. May 2011 um 12:11 Uhr

RSS feed for comments on this post. | TrackBack URI

Leave a comment

XHTML ( You can use these tags): <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> .