Tuesday, December 07, 2010

Monadic fun: real life state monads

I am deepening my functional programming skills these days and becoming master of the state monad (computational expression) in F#. I had read much about monads but need to conclude that 95% of what is written is not about "real programs". The state monad is always presented within the scope of a single state and rarely with error management. But real life is about having many state dependent algorithms that intertwine and having an error management that keeps you within your main paradigms.

Here are a few things to care about:
1) Assume that the state is carrying multiple payloads, usually one per algorithm. Use accessors to convert that "global" monad state to each algorithmic specific state. You'll need a get and map accessor for each "sub-state". At the top level, when assembling your different modules you instantiate algorithmic specific monads with their accessors; Internally they are working on their specific state, but in reality they are always accessing the single global common state of the monad. A good example: design a parser and type inference algorithm separately, based on the state monad. Then bring the two together to catch type errors during the parsing.
2) Bring all errors into a single application wide error type. Like the global state concept, you have algorithmic specific error types, then use an error specific accessor to bring the local error type into a broader global error management scheme.
3) If an algorithm are not persistent, but only local, then you do not need to keep its state in the global state. In this cases, you locally augment the monad's state with the algorithmic local content, to then revert back to the global state on end of the algorithm. For example, keep the "normal state" in one element of a tuplet, and use the other to store the local state. The following monad "transformers" are used bridge the compatibility between the global state monads and local augmented form:

let rec mapErrState f = function
| ErrMsg(et,s) -> ErrMsg(et, f s)
| ErrOr(e1, e2) -> ErrOr(mapErrState f e1, mapErrState f e2)
| ErrAnd(e1, e2) ->ErrAnd(mapErrState f e1, mapErrState f e2)
| ErrTag(et, e) -> ErrTag(et, mapErrState f e)



let map1M m :_ -> StateR<_,_,_> = fun a -> toState (fun (s,x) ->
match runState (m a) s with
| Success (v,s') ->
Success (v,(s',x))
| Fail e ->
Fail (mapErrState (fun s'->(s',x)) e)
)

let map2M m :_ -> StateR<_,_,_> = fun a -> toState (fun (x,s) ->
match runState (m a) s with
| Success (v,s') ->
Success (v,(x,s'))
| Fail e ->
Fail (mapErrState (fun s'->(x,s')) e)
)

let pairM t (m: _ -> StateR<_,_,_>) : _ -> StateR<_,_,_>= fun a -> toState (fun s ->
match runState (m a) (t, s) with
| Success (v, (t',s')) ->
Success ((v,t'), s')
| Fail e ->
Fail (mapErrState (fun (t',s') -> s') e)
)
You'll note that my failure type stores states (makes easier debugging), this is why I need to map through the errors.

Update: an earlier visitor may have noticed that I have updated this code to work with a "function that returns state monads" and not directly the state monad. There is a reason for this but it will need to wait for a later post.

No comments: