3b5312c155d0a1552bfd9d0cd4f8b400aea8b2e6
1 [[!toc]]
4 ===========================
11                 env -> 'a;;
12         let unit (a : 'a) : 'a reader =
13                 fun e -> a;;
15                 fun e -> (fun a -> f a e) (u e);;
17 We've just beta-expanded the familiar `f (u e) e` into `(fun a -> f a
18 e) (u e)`. We did that so as to factor out the parts where any Reader monad is
19 being supplied as an argument to another function. That will help make some patterns that are coming up more salient.
23 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 sometimes works. It's what we did in the hints to GSV assignment, where as we said, we "combined State and Set in an ad hoc way."
25 But there are two problems: (1) It's cumbersome having to work with *both* `reader_bind` and `M.bind`. It'd be nice to figure out some systematic way to connect the plumbing of the different monadic layers, 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 will let us do.
27 (2) For some combinations of monads, the best way to implement a Tish monadic wrapper around an inner M monad won't be equivalent to either an `('a m) t` or an `('a t) m`. It will be a tighter intermingling of the two. So some natural activities will remain out of reach until we equip ourselves to go beyond `('a m) t`s and so on.
29 What we want in general are monadic transformers. For example, 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`, together with the Reader patterns for unit and bind, to define a new monad ReaderT(M) that fuses the behavior of Reader and M.
33 Here's how it's implemented:
37         (* We're not giving valid OCaml code, but rather something
38          * that's conceptually easier to digest.
39          * How you really need to write this in OCaml is more circuitous...
42          * for some details. *)
45                 env -> 'a M;;
46         (* this _happens_ also to be the type of an ('a M) reader
47          * but as we noted, you can't rely on that pattern always to hold *)
49         let unit (a : 'a) : 'a readerT(M) =
50                 fun e -> M.unit a;;
52         let bind (u : 'a readerT(M)) (f : 'a -> 'b readerT(M)) : 'b readerT(M) =
53                 fun e -> M.bind (u e) (fun a -> f a e);;
55 Notice the key differences: where before `unit` was implemented by a function that just returned `a`, now we
56 instead return `M.unit a`. Where before `bind` just supplied value `u e`
57 of type `'a reader` as an argument to a function, now we instead
58 `M.bind` the corresponding value to the function. Notice also the differences
59 in the types.
61 What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
63         type 'a identity = 'a;;
64         let unit (a : 'a) : 'a = a;;
65         let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
67 and you used the ReaderT transformer to wrap the Identity monad inside Readerish packaging. What do you suppose you would get?
69 The relations between the State monad and the StateT monadic transformer are parallel:
73         type 'a state =
74                 store -> ('a * store);;
76         let unit (a : 'a) : 'a state =
77                 fun s -> (a, s);;
79         let bind (u : 'a state) (f : 'a -> 'b state) : 'b state =
80                 fun s -> (fun (a, s') -> f a s') (u s);;
82 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:
86         type 'a stateT(M) =
87                 store -> ('a * store) M;;
88         (* notice this is not an ('a M) state *)
90         let unit (a : 'a) : 'a stateT(M) =
91                 fun s -> M.unit (a, s);;
93         let bind (u : 'a stateT(M)) (f : 'a -> 'b stateT(M)) : 'b stateT(M) =
94                 fun s -> M.bind (u s) (fun (a, s') -> f a s');;
97 Do you see the pattern? Where before `unit` was implemented by a function that returned an `'a * store` value, now we instead use `M.unit` to return an `('a * store) M` value. Where before `bind` supplied an `'a state` value `(u s)` as an argument to a function, now we instead `M.bind` it to that function.
99 Once again, what do you think you'd get if you wrapped StateT monadic packaging around an Identity monad?
102 We spell out all the common monads, their common dedicated operations (such as `lookup`- and `shift`-like operations for the Reader monad), and monad transformer cousins of all of these, in an OCaml [[monad library]]. Read the linked page for details about how to use the library, and some design choices we made. Our [[State Monad Tutorial]] gives some more examples of using the library.
104 When a T monadic layer encloses an inner M monad, the T's interface is the most exposed one. To use operations defined in the inner M monad, you'll have to "elevate" them into the outer T packaging. Haskell calls this operation `lift`, but we call it `elevate` because the term "lift" is already now too overloaded. In our usage, `lift` (and `lift2`) are functions that bring non-monadic operations into a monad; `elevate` brings monadic operations from a wrapped monad out into the wrapping.
106 Here's an example. Suppose `S` is an instance of a State monad:
109         # module S = State_monad(struct type store = int end);;
111 and `MS` is a MaybeT wrapped around `S`:
113         # module MS = Maybe_monad.T(S);;
115 Then if you want to use an `S`-specific monad like `puts succ` inside `MS`, you'll have to use `MS`'s `elevate` function, like this:
117         # MS.(...elevate (S.puts succ) ...)
119 Each monad transformer's `elevate` function will be defined differently. They have to obey the following laws:
121 *       `Outer.elevate (Inner.unit a) <~~> Outer.unit a`
122 *       `Outer.elevate (Inner.bind u f) <~~> Outer.bind (Outer.elevate u) (fun a -> Outer.elevate (f a))`
124 We said that when T encloses M, you can rely on T's interface to be most exposed. That is intuitive. What you cannot also assume is that the implementing type has a Tish structure surrounding an Mish structure. Often it will be reverse: a ListT(Maybe) is implemented by a `'a list option`, not by an `'a option list`. Until you've tried to write the code to a monadic transformer library yourself, this will probably remain counter-intuitive. But you don't need to concern yourself with it in practise. Think of what you have as a ListT(Maybe); don't worry about whether the underlying implementation is as an `'a list option` or an `'a option list` or as something more complicated.
126 Notice from the code for StateT, above, that an `'a stateT(M)` is not an `('a M) state`; neither is it an `('a state) M`. The pattern by which we transform the types from a Blah monad to a BlahT monad transformer is:
128         't0                  --->  't0 M
129         't1 -> 't0           --->  't1 -> 't0 M
130         ('t1 -> 't0) -> 't0  --->  ('t1 -> 't0 M) -> 't0 M
132 Ken Shan's paper [Monads for natural language semantics](http://arxiv.org/abs/cs/0205026v1) (2001) discusses how to systematically move from some base 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 that form; List for example doesn't.)
134 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 StateT and so on should be; having figured that out, plain State would follow as the simple case where StateT is parameterized on the Identity monad.
136 Apart from whose interface is outermost, the behavior of a StateT(Maybe) and a MaybeT(State) will partly coincide. But in certain crucial respects they will diverge, and you need to think carefully about which behavior you want and what the appropriate layering is for your needs. Consider these examples:
138         # module MS = Maybe_monad.T(S);;
139         # module SM = S.T(Maybe_monad);;
140         # MS.(run (elevate (S.puts succ) >> zero () >> elevate S.get >>= fun cur -> unit (cur+10) )) 0;;
141         - : int option * S.store = (None, 1)
142         # MS.(run (elevate (S.puts succ) >> zero () >> elevate (S.put 5) )) 0;;
143         - : unit option * S.store = (None, 1)
145 Although we have a wrapped `None`, notice that the store (as it was at the point of failure) is still retrievable.
147         # SM.(run (puts succ >> elevate (Maybe_monad.zero ()) >> get >>= fun cur -> unit (cur+10) )) 0;;
148         - : ('a, int * S.store) Maybe_monad.result = None
150 When Maybe is on the inside, on the other hand, a failure means the whole computation has failed, and even the store is no longer available.
152 <!--
153         # ES.(run( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i -> unit(i+10) )) 0;;
154         - : int Failure.error * S.store = (Failure.Error "bye", 1)
155         # SE.(run( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i -> unit(i+10) )) 0;;
156         - : (int * S.store) Failure.result = Failure.Error "bye"
157         # ES.(run_exn( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i -> unit(i+10) )) 0;;
158         Exception: Failure "bye".
159         # SE.(run_exn( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i -> unit(i+10) )) 0;;
160         Exception: Failure "bye".
161 -->
163 Here's an example wrapping Maybe around List, and vice versa:
167         # ML.(run (plus (zero ()) (unit 20) >>= fun i -> unit (i+10)));;
168         - : ('_a, int) ML.result = [Some 30]
170 When List is on the inside, the failed results just get dropped and the computation proceeds without them.
172         # LM.(run (plus (elevate (Maybe_monad.zero ())) (unit 20) >>= fun i -> unit (i+10)));;
173         - : ('_a, int) LM.result = None
175 On the other hand, when Maybe is on the inside, failures abort the whole computation.
177 <!--
178         # EL.(run( plus (throw "bye") (unit 20) >>= fun i -> unit(i+10)));;
179         - : int EL.result = [Failure.Error "bye"; Failure.Success 30]
180         # LE.(run( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i -> unit(i+10)));;
181         - : int LE.result = Failure.Error "bye"
182         # EL.(run_exn( plus (throw "bye") (unit 20) >>= fun i -> unit(i+10)));;
183         Exception: Failure "bye".
184         # LE.(run_exn( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i -> unit(i+10)));;
185         Exception: Failure "bye".
186 -->
188 This is fun. Notice the difference it makes whether the second `plus` is native to the outer `List_monad`, or whether it's the inner `List_monad`'s `plus` elevated into the outer wrapper:
192         # LL.(run(plus (unit 1) (unit 2) >>= fun i -> plus (unit i) (unit(10*i)) ));;
193         - : ('_a, int) LL.result = \[[1; 10; 2; 20]]
194         # LL.(run(plus (unit 1) (unit 2) >>= fun i -> elevate L.(plus (unit i) (unit(10*i)) )));;
195         - : ('_a, int) LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
200 ---------------
202 *       This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.grabmueller.de/martin/www/pub/Transformers.pdf)
208 ===========
212 So how does our `Tree_monad` behave? Simplified, its implementation looks something like this:
216         type 'a tree =
217                 Leaf of 'a | Node of ('a tree) * ('a tree);;
219         let unit (a: 'a) : 'a tree =
220                 Leaf a;;
222         let rec bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
223             match u with
224             | Leaf a -> f a;;
225             | Node (l, r) ->
226                         let l' = bind l f in
227                         let r' = bind r f in
228                         Node (l', r')
230 Recall how `bind` works for the List monad. If you have a list:
232         let u = [1; 2; 4; 8];;
234 and a function `f` such that:
236         f 1 ~~> []
237         f 2 ~~> 
238         f 4 ~~> [2; 4]
239         f 8 ~~> [2; 4; 8]
241 then `list_bind u f` would be `concat [[]; ; [2; 4]; [2; 4; 8]]`, that is `[2; 2; 4; 2; 4; 8]`. It splices the lists returned by `f` into the corresponding positions in the original list structure. The `tree_bind` operation works the same way. If `f'` maps `2` to the tree `Leaf 2` and `8` to the tree `Node (Leaf 2, Node (Leaf 4, Leaf 8))`, then binding the tree `u` to `f'` will splice the trees returned by `f'` to the corresponding positions in the original structure:
243          u
244          .                    .
245         _|__  >>=  f' ~~>    _|__
246         |  |                 |  |
247         2  8                 2  .
248                                _|__
249                                |  |
250                                2  .
251                                  _|__
252                                  |  |
253                                  4  8
255 Except, as we mentioned, our implementation of the Tree monad incorporates an Optionish layer too. So `f' 2` should be not `Leaf 2` but `Some (Leaf 2)`. What if `f'` also mapped `1` to `None` and `4` to `Some (Node (Leaf 2, Leaf 4))`. Then binding the tree `Node (Leaf 1, Node (Leaf 2, Leaf 4))` (really the tree itself needs to be wrapped in a `Some`, too, but let me neglect that) to `f'` would delete the branch corresponding to the original `Leaf 1`, and would splice in the results for `f' 2` and `f' 4`, yielding:
257          .
258         _|__  >>=  f' ~~>
259         |  |
260         1  .                    .
261           _|__                 _|__
262           |  |                 |  |
263           2  4                 2  .
264                                  _|__
265                                  |  |
266                                  2  4
268 As always, the functions you bind an `'a tree` to need not map `'a`s to `'a tree`s; they can map them to `'b tree`s instead. For instance, we could transform `Node (Leaf 1, Node (Leaf 2, Leaf 4))` instead into `Node (Leaf "two", Node (Leaf "two", Leaf "four"))`.
270 As we [mention in the notes](/monad_library), our monad library encapsulates the implementation of its monadic types. So to work with it you have to use the primitives it provides. You can't say:
272         # Tree_monad.(orig_tree >>= fun a -> match a with
273             | 4 -> Some (Node (Leaf 2, Leaf 4))
274             | _ -> None);;
275         Error: This expression has type int Tree_monad.tree option
276                    but an expression was expected of type ('a, 'b) Tree_monad.m
278 You have to instead say something like this:
280         # Tree_monad.(orig_tree >>= fun a -> match a with
281             | 4 -> plus (unit 2) (unit 4)
282             | _ -> zero () );;
283         - : ('_a, int) Tree_monad.m = <abstr>
287 How is all this related to our tree\_monadize function?
288 -------------------------------------------------------