Thursday, December 13, 2012

Fun with higher order monadic construction (F#, part 1)

Higher order X really means that X is used in something bigger. So when I say higher monadic construction, I mean that we use monads in more than the bind function or creating them with return like functions. Note that the intro post to this series, shows how you can lift monads, that is a higher order operation!. Now that we have a stateful maybe monad with error management (see earlier post) we can bring in higher order operators that are similar to the bind, they control sequencing, but in a different way. The maybe monad, stateful or not, has a logical notion, you either do things or not, so it makes sense that start with a focus on boolean operators. Note that these are really operators for computational logic not really boolean logic.
We start with the OR operator. Note how the transactional part of the state goes through the "true" part of the computation, while the error state goes through the "false" part of the code. (This is what I call a trace centric coding style).
let (|||) m1 m2 = SM (fun ((s,err) as sr) ->
    let (optX1, ((s1,err1) as sr1)) = run m1 sr
    match optX1 with
    | Some _ -> (optX1, sr1)
    | None   ->
        let (optX2, (s2,err2)) = run m2 (s, err1)
        match optX2 with
        | Some _ -> (optX2, (s2, err))
        | None   -> (None, (s, err2)))
Now I can show off its behavior by trying to fetch one or an other value from the stateful map (see this post for details), it fails becaue the map only has values associated to "a" and "b": 
let test16 =
    optState {
        let! a = get7 "a"
        let! b = (get7 "x") ||| (get7 "y")
        do! set7 ("c",(a+b))
        let! counter = increment8
        return counter
        }
The interest here is the programming style: we either do one part of the expression or the other. But more importantly that we have defined the OR operator to capture errors as a state. So running (run test16 (testState1,[]) ) the above test will produce:
(null, ({keyValues = map [("a", 1.0); ("b", 2.0)];
         counter = 100;}, ["key "y" not found"; "key "x" not found"]))
Which is nice because it contains both failures of lookup.
To the contrary, the following variation of our test:
let test17 =
    optState {
        let! a = get7 "a"
        let! b = (get7 "x") ||| (get7 "b")
        do! set7 ("c",(a+b))
        let! counter = increment8
        return counter
        }
Fails first with "x" to then succeed with "b" and so return no error:
  (Some 101, ({keyValues = map [("a", 1.0); ("b", 2.0); ("c", 3.0)];
               counter = 101;}, []))
With the OR operator we want an AND operator, defined as follows:

let (&&&) m1 m2 = SM (fun ((s,err) as sr) ->
    let (optX1, sr1) = run m1 sr
    match optX1 with
    | Some x1 ->
        let (optX2, sr2) = run m2 sr1
        match optX2 with
        | Some x2 -> (Some(x1,x2), sr2)
        | None   -> (None, sr2)
    | None   ->
        (None, sr1))
The code is much more simple than the OR because we do not need to take the state appart as we depend on each of the monadic arguments to do that for us.
As we want to get "a" AND get "b" we can write are test code as following:
let test17 =
    optState {
        let! (a, b) = (get7 "a") &&& (get7 "b")
        do! set7 ("c",(a+b))
        let! counter = increment8
        return counter
        }
This puts the focus on the fact that this definition of the AND operator is returning a tuplet of the two successfuly return values.  Now again we can see it manage errors:
let test18 =
    optState {
        let! (a, b) = (get7 "a") &&& (get7 "x")
        do! set7 ("c",(a+b))
        let! counter = increment8
        return counter
        }

When run will produce the expected initial "transactional" state with the error state:
  (null, ({keyValues = map [("a", 1.0); ("b", 2.0)];
           counter = 100;}, ["key "x" not found"]))
The good thing about this version of the AND is that the left and right arguments can be returning different types.  Yet often we have lists of things to do, So having a similar set of boolean like operators to work with lists of monads would be a nice thing.
I'll show you how to do that in my next post (as my daughter's drumming lesson is coming to an end so that will be all for this post)!

Wednesday, December 12, 2012

Error management with state monads

The Maybe, Option in F#, monad returns only Nothing/None when "things go bad".
In real life we want to return details of what when wrong.

The other day someone asked me: how do I choose if something should go in the return part of the state monad, or in the state itself? Last post I showed you how to combine the Maybe and State monad. The natural next step is to extend things further in order to allow some form of error management; This provides more comfort than the  "all or nothing" standard behavior of the Maybe monad;  And, is exactly a case where we can choose either to return error information, or to augment the state to store error state.

Returning the error seems the natural thing to do. The idea is to use an Either like type, which either returns what you want normally, or the error status.  In F#, the Maybe monad is either returning "Some value" or "None",  the idea would be instead to return something like "Ok value" or "Failed error" based on a type declaration like:

type ReturnWithErr<'t,'err> =
| Ok     of  't
| Failed of  'err

 The problem with this, is that it brings you back to programming with return errors. One of the reasons why exception were invented is that it is a painful effort to decide what to do with each of these returned error.

The magic of functional programming is that we can "swivel" between a functional and state view. (I'll need to make a post on this concept, very important). Therefore we can "decide" that our error management is stateful. And as this is a local state that is caried around by the monad (it is "local" enough that it is ok to put things in it like the current error state).

We need to do better than using the basic state monad because it removes failed states, and therefore would remove any "state of error" that we might try to keep. The idea is then to split the state into two parts:
  • the "transactional" state that is lost on failure
  • the "error" state that is kept on failure
Normally the "error" state is only updated in case of error. Although you could imagine having a "not" like operator that clears the error state.

We know enough to write some code. In the previous post, I showed you how the bind operator of the stateful Maybe monad needs to track one state. Now we write a bind works with the two states instead of one. From the orginal state monad perspective there is still only one state but it is a tuplet transactionalState*errorState :

let bindOpt m g =
    SM(fun ((s,err) as sr) ->
    let (rf, ((s2,err2) as sr2)) = run m sr
    match rf with
    | Some rfv ->
        let (rg, ((s3,err3) as sr3)) = run (g rfv) sr2
        match rg with
        | Some _ ->
            (rg, sr3)
        | None ->
            (None, (s,err3))
    | None ->
        (None, (s,err2)))

It pretty much does what I mentioned above: the transactional state follows the "ok" path (states s, s2, and s3), the error state follow the failed path (state err, err2, and err3)

We want a few helper functions:

let getState f = SM (fun ((s,err) as sr) -> (Some(f s), sr))
let mapState f = SM (fun(s,err) -> (Some(), (f s,err)))
let ret x = SM (fun s -> (Some x,s))
let retSome mapErr optX = SM (fun((s,err) as sr) ->
    match optX with
    | Some _ -> (optX, sr)
    | None ->(None, (s, mapErr err)))
let retNone mapErr = SM (fun(s,err) -> (None, (s, mapErr err)))

And now we can wrap our monad in the "do" notation semantic of F#:

type OptState() =
    member inline b.Bind (m, f) =  bindOpt m f
    member inline b.Combine(m1, m2) = bindOpt m1 (fun _ ->m2)
    member inline b.Return x = ret x
    member inline b.ReturnFrom m = m

To demontrate the concept, I assume my error state is just a list of strings. So I need a little helper function to add to this list:



let cons x t = x :: t
And now I can refactor the "get" function (see previous post):
let get7 key =
    optState {
        let! kv = getState getKeyValues
        let! value = retSome (cons (sprintf "key %A not found" key)) (Map.tryFind key kv)
        return value
        }
If the get function fails, the error state will hold a list of string where the failure is reported. In this next example, the get fails because "x" is not part of the state map (again see last post the map only has keys "a" and "b"):
let test15 =
    optState {
        let! a = get7 "a"
        let! b = get7 "x"
        do! set7 ("c",(a+b))
        let! counter = increment8
        return counter
        }
Running this, run test15 (testState1,[]), gives:
(null, ({keyValues = map [("a", 1.0); ("b", 2.0)];
           counter = 100;}, ["key "x" not found"]))
And it has the error message in the error state! One of the key concept of the arrow is that a flow of information gets modified, while the other part stays the same. Augmenting state monads as shown above is really about applying the same idea. Next time I'll talk above higher order monadic constructions. We can again use our simple example for that. 
 

Saturday, December 01, 2012

Introduction to stateful monads

I went to my first Zurich FSharp meeting the other day and made a presentation on how to program with state monads in F#.

The presentation is designed to pull you off the ground, to a higher order programming style, using the state and maybe monad as stepping stones. It finishes with stateful lifting.

Here is a link to a slightly improved version: youtube .

Link to sources are below but I would recommend that if you really do not know this type of programming and want to learn, then you should type it back in and allow yourself some creative liberty. This is usually a much better way to learn, than to just copy code!

You can watch it here if you want:

http://files.meetup.com/2794852/ModularStateMonadsInFSharp.pdf
http://files.meetup.com/2794852/XState1.fs
http://files.meetup.com/2794852/XState2.fs
http://files.meetup.com/2794852/Script.fsx