F# is a multi-paradigm language which lets you program in both a functional pure manner and a imperative mutational way.  With F#’s growing popularity many .NET programmers are trying out the language and are able to get started quickly because they can take their imperative programming  knowledge along with them.  This flexibility is a great feature of F# but it can often distract new functional programmers from learning and benefiting from good functional programming techniques.

One of the advantages of functional programming is the emphasis on small, and pure functions.  Pure functions are functions which meet two criteria:

1. Given the same arguments will always return the same result.
2. Have no observable side effects. (Such as mutations of objects or variables)

While a language like Haskell makes it very hard to ignore these criteria, F# is a more lenient.   Writing small pure functions provides leads to very readable and testable programs.

Writing pure functions is difficult for an imperative programmer because using side affects is engrained in the paradigm.  Obviously, not every function in your application can be pure since you need to do some IO at some point but you can architect your program to isolate IO. Once you isolate IO the other type of mutations is  updating the application state.  In OO programming this state is the fields and properties of a class.  Each method in the class can access and update these fields thereby updating the state.

So, how do you update state similarly in a purely functional way? Simply, every function which wants to read or update state must take its state as an argument and must return the state as part of its result. Consider a simple program which keeps track of the position of an object. The position consists of an x and y coordinate.  This state can be represented as a tuple (x,y).The program has of a couple of functions which act on this state: moveUp and  moveRight.

Moving the object up and to the right using mutable state would look like

let mutable pos = (5,5)

let moveUp () = pos <- (fst pos, snd pos - 1)
let moveRight() = pos <- (1 + fst pos, snd pos)

moveUp()
moveRight()

In order to do the same with immutable state we need to change the functions so that they take the current position and return the new position.  moveUp and moveRight would change to

let moveUp pos = (fst pos, snd pos - 1)
let moveRight pos = (1 + fst pos, snd pos)

And executing the actions of moving up and to left changes to

let pos = moveUp (5,5)
let newPos = moveRight pos

However, this can get a bit ugly (especially if we wanted to chain many moves in a row) since you are  passing the result of one function into the next.  In this case we can make use of F#’s forward pipe operator (|>) to make this a bit neater.  This operator takes the results of one function and passes it to the next.  The code now becomes

let pos = (5,5) |>
          moveUp   |>
          moveRight

This is very clean and it looks like we are just declaring actions we want and the state gets shuffled through on its own.

This technique works really well when each action is simple and just takes and returns the state.  However, it can get complicated fast when trying to do something more complex such as:

• Calling a function which does not take and return the state. A function like this needs to be wrapped in another function that will take and return the state.
• Allowing the functions in the chain have a return value in addition to the state. To do this you need to expand the definition of state to include a generic return value.

Modifying the object moving program to show the above complexities we get a new program which will move the object up twice then check its position then depending where it is either move it right or up.

type PosAndStuff<'a> = { value: 'a; pos: int * int }

let a = {value = 4; pos = (1,1)}

let moveUp state = { value = (); pos = (fst state.pos, snd state.pos - 1)}
let moveRight state = { value = (); pos = (fst state.pos + 1, snd state.pos)}

let test pos1 pos2 = fst pos1 = fst pos2 || snd pos1 = snd pos2
let moveUpAndTest state testPos =
    if test state.pos testPos
    then { value = true; pos = (fst state.pos, snd state.pos - 1)}
    else { value = false; pos = (fst state.pos, snd state.pos - 1)}

let result = { value = (); pos = (5,5) } |>
             moveUp |>
             (fun state ->
                let newState = moveUpAndTest state (5,4)
                if newState.value
                then moveRight newState
                else moveUp newState
             )

The above program is very verbose since it has to manage the state.  But there is an elegant solution that makes managing immutable state easy, the State monad. The State monad can be implemented using one of F#’s most powerful language constructs: Computation Expressions(CE). CE’s are a syntax around the monadic operations of Bind and Return.  Using CE’s we can create a State monad which makes stateful programming both elegant and convenient.

This is an implementation of the State monad in F#:

type State<'st,'a> =
    | Ok of  'a * 'st
    | Error of ErrorState
and ErrorState = string
and StateMonadBuilder() =
    member b.Return(x) = fun s -> Ok (x, s)
    member b.ReturnFrom(x) = x
    member b.Error msg = fun _ -> Error msg
    member b.Bind(p, rest) =
        fun state ->
                 let result = p state in
                 match result with
                 | Ok (value,state2) -> (rest value) state2
                 | Error msg -> Error msg  

    member b.Get () = fun state -> Ok (state, state)
    member b.Put s = fun state -> Ok ((), s)

let state = StateMonadBuilder()

The state monad provides many benefits over the previous examples.

1. It makes state implicit so  you can just ask for it when you need it and ignore it when you don’t.
2. It removes the need for boiler plate code to glue expressions together with their state
3. It makes use of built in F# language support for monadic expressions which aids in expressiveness and readability.

Using the state monad we can rewrite the previous program as

let moveUp () =
    state {
        let! pos = state.Get()
        return! state.Put(fst pos, snd pos - 1)
    }

let moveRight () =
    state {
        let! pos = state.Get()
        return! state.Put(fst pos + 1, snd pos)
    }

let test pos1 pos2 = fst pos1 = fst pos2 || snd pos1 = snd pos2

let moveUpAndTest testPos =
    state {
        do! moveUp()
        let! pos = state.Get()
        return test pos testPos
    }

let run () =
    state {
        do! moveUp()
        let! res =  moveUpAndTest (5,4)
        if res
        then
            do! moveRight ()
        else
            do! moveUp()
    }

let result = match run () (5,5) with
             | Ok (_,pos) -> pos
             | Error _ -> (0,0)

The beauty of the state monad is seen in the run method on line 22 . No code in this method explicitly does anything with the programs’ state.  It just calls other functions and all the state passing code is handled for us. This enables us to write code that leverages immutable state as easily as we write code that updates mutable state.

While you may not always need the full power of the State monad, it along with explicit state passing are key tools for writing functional programs. With them you can approach many complex problems without the need for mutable state.

Related Links

• Regex based Lexer with F#
• The State Monad
• Pure Function
• Computation Expressions