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: F#, monad, state monad
let rec labelTreeMS t = match t with
Why not
let rec labelTreeMS = function
?
Comment by guest — Sunday, 25. October 2009 um 12:08 Uhr
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
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