monad_transformers: develop

[lambda.git] / monad_transformers.mdwn

diff --git a/monad_transformers.mdwn b/monad_transformers.mdwn
index b72c035..c8072cf 100644 (file)
--- a/monad_transformers.mdwn
+++ b/monad_transformers.mdwn
@@ -1,5 +1,5 @@
 
 

-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 adds a Reader monad layer to it. The way these are defined parallels the way the single-layer versions are defined. For example, here's the Reader monad:
+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 *)
 
 
        (* monadic operations for the Reader monad *)
 


@@ -11,11 +11,16 @@ So far, we've defined monads as single-layered things. Though in the Groenendijk
                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
                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)`, in order to factor out the parts where any Reader monad is
-being supplied as an argument to another function, as illustrated in
-the `bind` function in the following example. Then if we want instead
-to add a Reader layer to some arbitrary other monad M, with its own
-M.unit and M.bind, here's how we do it:
+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 *)
 
 
        (* monadic operations for the ReaderT monadic transformer *)
 


@@ -24,14 +29,14 @@ M.unit and M.bind, here's how we do it:
         * How you really need to write this in OCaml is more circuitous...
         * see http://lambda.jimpryor.net/code/tree_monadize.ml for some details. *)
 
         * 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 ('a, M) readerT =
+       type (M, 'a) readerT =

                env -> 'a M;;
                env -> 'a M;;

-       (* this is just an 'a M reader; but don't rely on that pattern to generalize *)
+       (* 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) : ('a, M) readerT =
+       let unit (a : 'a) : (M, 'a) readerT =

                fun e -> M.unit a;;
 
                fun e -> M.unit a;;
 

-       let bind (u : ('a, M) readerT) (f : 'a -> ('b, M) readerT) : ('b, M) readerT =
+       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
                fun e -> M.bind (u e) (fun v -> f v e);;
 
 Notice the key differences: where before we just returned `a`, now we


@@ -46,7 +51,7 @@ What is the relation between Reader and ReaderT? Well, suppose you started with
        let unit (a : 'a) : 'a = a;;
        let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
 
        let unit (a : 'a) : 'a = a;;
        let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
 

-and you used the ReaderT transformer to add a Reader monad layer to the Identity monad. What do you suppose you would get?
+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:
 
 
 The relations between the State monad and the StateT monadic transformer are parallel:
 


@@ -65,17 +70,27 @@ We've used `(fun (a, s') -> f a s') (u s)` instead of the more familiar `let (a,
 
        (* monadic operations for the StateT monadic transformer *)
 
 
        (* monadic operations for the StateT monadic transformer *)
 

-       type ('a, M) stateT =
+       type (M, 'a) stateT =

                store -> ('a * store) M;;
                store -> ('a * store) M;;

-       (* notice this is not an 'a M state *)
+       (* notice this is not an ('a M) state *)

 
 

-       let unit (a : 'a) : ('a, M) stateT =
+       let unit (a : 'a) : (M, 'a) stateT =

                fun s -> M.unit (a, s);;
 
                fun s -> M.unit (a, s);;
 

-       let bind (u : ('a, M) stateT) (f : 'a -> ('b, M) stateT) : ('b, M) stateT =
+       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');;
 
                fun s -> M.bind (u s) (fun (a, s') -> f a s');;
 

-Do you see the pattern? Where ordinarily we'd return an `'a` value, now we instead return an `'a M` value. Where ordinarily we'd supply a `'a state` value as an argument to a function, now we instead `M.bind` it to that function.
+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?
+
+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.
 
 
 Okay, now let's do the same thing for our Tree monad.
 


@@ -95,13 +110,13 @@ Okay, now let's do the same thing for our Tree monad.
        (* monadic operations for the TreeT monadic transformer *)
        (* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)
 
        (* monadic operations for the TreeT monadic transformer *)
        (* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)
 

-       type ('a, M) treeT =
+       type (M, 'a) treeT =

                'a tree M;;
 
                'a tree M;;
 

-       let unit (a: 'a) : ('a, M) tree =
+       let unit (a: 'a) : (M, 'a) tree =

                M.unit (Leaf a);;
 
                M.unit (Leaf a);;
 

-       let rec bind (u : ('a, M) tree) (f : 'a -> ('b, M) tree) : ('b, M) tree =
+       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' ->
            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' ->