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

1 comment:

M.Z. said...

Hi James,
I love your blog and look forward to your postings!
M.Z.