Merge branch 'pryor'

[lambda.git] / monad_transformers.mdwn

So far, we've defined monads as single-layered things. Though in the Groenendijk, Stokhoff, and Veltmann homework, we had to figure out how to combine Reader, State, and Set monads in an ad-hoc way. In practice, one often wants to combine the abilities of several monads. Corresponding to each monad like Reader, there's a corresponding ReaderT **monad transformer**. That takes an existing monad M and wraps a Reader monad box around it. The way these are defined parallels the way the single-layer versions are defined. For example, here's the Reader monad:

        (* monadic operations for the Reader monad *)

        type 'a reader =
                env -> 'a;;
        let unit (a : 'a) : 'a reader =
                fun e -> a;;
        let bind (u: 'a reader) (f : 'a -> 'b reader) : 'b reader =
                fun e -> (fun v -> f v e) (u e);;

We've just beta-expanded the familiar `f (u e) e` into `(fun v -> f v
e) (u e)`. We did that so as to factor out the parts where any Reader monad is
being supplied as an argument to another function. That will help make some patterns that are coming up more salient.

That was the plain Reader monad. Now if we want instead to wrap some other monad M inside Reader packaging. How could we do it?

Well, one way to proceed would be to just let values of the other monad M be the `'a` in your `'a reader`. Then you could apply `reader_bind` to get at the wrapped `'a M`, and then apply `M.bind` to get at *its* wrapped `'a`. This works. It's what we did in the hints to GSV assignment, where we said we "combined State and Set in an ad hoc way."

It's be nice to figure out some systematic way to connect the plumbing of the different monadic layers, though, so that we could have a *single* `bind` that took our `'a M_inside_Reader`, and sequenced it with a single `'a -> 'b M_inside_Reader` function. Similarly for `unit`. This is what the ReaderT monad transformer lets us do.

A ReaderT transformer will be parameterized not just on the type of its innermost contents `'a`, but also on the monadic box `M` that wraps `'a`. It will make use of monad `M`'s existing operations `M.unit` and `M.bind`. Here's how we do it:

        (* monadic operations for the ReaderT monadic transformer *)

        (* We're not giving valid OCaml code, but rather something
         * that's conceptually easier to digest.
         * How you really need to write this in OCaml is more circuitous...
         * see http://lambda.jimpryor.net/code/tree_monadize.ml for some details. *)

        type (M, 'a) readerT =
                env -> 'a M;;
        (* this happens also to be the type of an ('a M) reader; but don't rely on that pattern to generalize *)

        let unit (a : 'a) : (M, 'a) readerT =
                fun e -> M.unit a;;

        let bind (u : (M, 'a) readerT) (f : 'a -> (M, 'b) readerT) : (M, 'b) readerT =
                fun e -> M.bind (u e) (fun v -> f v e);;

Notice the key differences: where before we just returned `a`, now we
instead return `M.unit a`. Where before we just supplied value `u e`
of type `'a reader` as an argument to a function, now we instead
`M.bind` the `'a reader` to that function. Notice also the differences
in the types.

What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:

        type 'a identity = 'a;;
        let unit (a : 'a) : 'a = a;;
        let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;

and you used the ReaderT transformer to wrap the Identity monad inside Reader packaging. What do you suppose you would get?

The relations between the State monad and the StateT monadic transformer are parallel:

        (* monadic operations for the State monad *)

        type 'a state =
                store -> ('a * store);;

        let unit (a : 'a) : 'a state =
                fun s -> (a, s);;

        let bind (u : 'a state) (f : 'a -> 'b state) : 'b state =
                fun s -> (fun (a, s') -> f a s') (u s);;

We've used `(fun (a, s') -> f a s') (u s)` instead of the more familiar `let (a, s') = u s in f a s'` in order to factor out the part where a value of type `'a state` is supplied as an argument to a function. Now StateT will be:

        (* monadic operations for the StateT monadic transformer *)

        type (M, 'a) stateT =
                store -> ('a * store) M;;
        (* notice this is not an ('a M) state *)

        let unit (a : 'a) : (M, 'a) stateT =
                fun s -> M.unit (a, s);;

        let bind (u : (M, 'a) stateT) (f : 'a -> (M, 'b) stateT) : (M, 'b) stateT =
                fun s -> M.bind (u s) (fun (a, s') -> f a s');;


Do you see the pattern? Where before we'd return an `'a * store` value, now we instead return an `('a * store) M` value. Where before we'd supply a `'a state` value `(u s)` as an argument to a function, now we instead `M.bind` it to that function.

Once again, what do you think you'd get if you wrapped a StateT monadic box around an Identity monad?

Notice that an `('a, M) stateT` is not an `'a M state`. The pattern by which the types are transformed from an Blah monad to a BlahT monad transformer is:

        't0                  --->  't0 M
        't1 -> 't0           --->  't1 -> 't0 M
        ('t1 -> 't0) -> 't0  --->  ('t1 -> 't0 M) -> 't0 M

Here's how this works for List and ListT:

        (* monadic operations for the List monad *)

        (* type 'a list is already pre-defined *)

        let unit (a : 'a) : 'a list =
                [a];;

        let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
                (fun v -> List.concat (List.map f v)) u

        (* monadic operations for the ListT monadic transformer *)

        type ('a, M) listT =
                'a list M;;

        let unit (a : 'a) : 'a list =
                [a];;

        let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
                (fun v -> List.concat (List.map f v)) u


Some comments before we proceed:

*       Ken Shan's paper [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (2001) discusses how to systematically move from some plain monads to the corresponding monad transformers. But as he notes, his algorithm isn't the only one possible, and it only applies to monads whose type has a certain form. (Reader and State have thet form, List for example doesn't.)
*       As best we know, figuring out how a monad transformer should be defined is still something of an art, not something that can be done mechanically. However, you can think that all of the art goes into deciding what ReaderT and so on should be; having figured that out, plain Reader would follow as the simple case where ReaderT is parameterized on the Identity monad.
*       We spell out all the common monads, their common dedicated operations (such as `lookup` for the Reader monad), and monad transformer cousins of all of these, in the following OCaml library: [[code/monads.ml]].


Okay, now let's do the same thing for our Tree monad.

        (* monadic operations for the Tree monad *)

        type 'a tree =
                Leaf of 'a | Node of ('a tree) * ('a tree);;

        let unit (a: 'a) : 'a tree =
                Leaf a;;

        let rec bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
            match u with
            | Leaf a -> f a;;
            | Node (l, r) -> (fun l' r' -> Node (l', r')) (bind l f) (bind r f);;

        (* monadic operations for the TreeT monadic transformer *)
        (* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)

        type (M, 'a) treeT =
                'a tree M;;

        let unit (a: 'a) : (M, 'a) tree =
                M.unit (Leaf a);;

        let rec bind (u : (M, 'a) tree) (f : 'a -> (M, 'b) tree) : (M, 'b) tree =
            match u with
            | Leaf a -> M.bind (f a) (fun b -> M.unit (Leaf b))
            | Node (l, r) -> M.bind (bind l f) (fun l' ->
                                                        M.bind (bind r f) (fun r' ->
                                                                M.unit (Node (l', r'));;

        (* problems --- why isn't Leaf clause simpler? trying to match u as if it were a tree. u and f's type is different than in tree_monadize. *)

Compare this definition of `bind` for the TreeT monadic transformer to our earlier definition of `tree_monadize`, specialized for the Reader monad:

        let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
            match t with
            | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
            | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
                               reader_bind (tree_monadize f r) (fun r' ->
                                 reader_unit (Node (l', r'))));;


*       This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.grabmueller.de/martin/www/pub/Transformers.pdf)
*       Read more about Monad Transformers [at the Haskell wikibook](http://en.wikibooks.org/wiki/Haskell/Monad_transformers)
*       Read more at [All About Monads](http://web.archive.org/web/20071106232016/haskell.org/all_about_monads/html/introIII.html). This link is to an archived version, the main link to haskell.org seems to be broken.