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

## Friday, 23. October 2009

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

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:

// 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

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)}

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))

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:

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

Tags: , ,

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