add cps_hint_*
[lambda.git] / topics / week9_monad_transformers.mdwn
1 So far, we've defined monads as single-layered boxes. 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 Readerish monad packaging around it. The way these are defined parallels the way the single-layer versions are defined. For example, here's the Reader monad:
2
3         (* monadic operations for the Reader monad *)
4
5         type 'a reader =
6                 env -> 'a;;
7         let mid (x : 'a) : 'a reader =
8                 fun e -> x;;
9         let mbind (xx: 'a reader) (k : 'a -> 'b reader) : 'b reader =
10                 fun e -> (fun x -> k x e) (xx e);;
11
12 We've just beta-expanded the familiar `k (xx e) e` into `(fun x -> k x e) (xx e)`. We did that so as to factor out the parts where the payload of any Reader value is being supplied as an argument to another function. That will help make some patterns that are coming up more salient.
13
14 That was the plain Reader monad. Now if we want instead to wrap some other monad M inside Readerish packaging. How could we do it?
15
16 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_mbind` to get at the wrapped `'a M`, and then apply `M.mbind` to get at *its* wrapped `'a`. This sometimes works.
17
18 But there are two problems: (1) It's cumbersome having to work with *both* `reader_mbind` and `M.mbind`. 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* `mbind` that took our `'a Reader_around_M`, and sequenced it with a single `'a -> 'b Reader_around_M` function. Similarly for `mid`. This is what the ReaderT monad transformer will let us do.
19
20 (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.
21
22 What we want in general are monadic transformers. For example, a ReaderT transformer will be parameterized not just on the type of its innermost payload `'a`, but also on the monadic box type `M` that wraps `'a`. It will make use of monad `M`'s existing operations `M.mid` and `M.mbind`, together with the Reader patterns for `mid` and `mbind`, to define a new monad ReaderT(M) that fuses the behavior of Reader and M.
23
24 To be clear: ReaderT isn't itself a monad. It's a kind of Readerish packaging (wrapping paper) that converts one monadic box M into another monadic box ReaderT(M).
25
26 Here's how it's implemented:
27
28         (* monadic operations for the ReaderT monadic transformer *)
29
30         (* We're not giving valid OCaml code, but rather something
31          * that's conceptually easier to digest.
32          * How you really need to write this in OCaml is more circuitous... *)
33
34         type 'a readerT(M) =
35                 env -> 'a M;;
36         (* this _happens_ also to be the type of an ('a M) reader
37          * but as we noted, you can't rely on that pattern always to hold *)
38
39         let mid (x : 'a) : 'a readerT(M) =
40                 fun e -> M.mid x;;
41
42         let mbind (xx : 'a readerT(M)) (k : 'a -> 'b readerT(M)) : 'b readerT(M) =
43                 fun e -> M.mbind (xx e) (fun x -> k x e);;
44
45 Notice the key differences: where before `mid x` was implemented by a function that just returned `x`, now we
46 instead return `M.mid x`. Where before `mbind` just supplied the payload `xx e`
47 of an `'a reader` as an argument to a function, now we instead
48 `M.mbind` the corresponding value to the function. Notice also the differences
49 in the types.
50
51 What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
52
53         type 'a identity = 'a;;
54         let mid (x : 'a) : 'a = x;;
55         let mbind (xx : 'a) (k : 'a -> 'b) : 'b = k xx;;
56
57 and you used the ReaderT transformer to wrap the Identity monad inside Readerish packaging. What do you suppose you would get?
58
59 The relations between the State monad and the StateT monadic transformer are parallel:
60
61         (* monadic operations for the State monad *)
62
63         type 'a state =
64                 store -> ('a * store);;
65
66         let mid (x : 'a) : 'a state =
67                 fun s -> (x, s);;
68
69         let mbind (xx : 'a state) (k : 'a -> 'b state) : 'b state =
70                 fun s -> (fun (x, s') -> k x s') (xx s);;
71
72 We've used `(fun (x, s') -> k x s') (xx s)` instead of the more familiar `let (x, s') = xx s in k x s'` in order to factor out the part where the payload of an `'a state` value is supplied as an argument to a function. Now StateT will be:
73
74         (* monadic operations for the StateT monadic transformer *)
75
76         type 'a stateT(M) =
77                 store -> ('a * store) M;;
78         (* notice this is not an ('a M) state *)
79
80         let mid (x : 'a) : 'a stateT(M) =
81                 fun s -> M.mid (x, s);;
82
83         let mbind (xx : 'a stateT(M)) (k : 'a -> 'b stateT(M)) : 'b stateT(M) =
84                 fun s -> M.mbind (xx s) (fun (x, s') -> k x s');;
85
86
87 Do you see the pattern? Where before `mid` was implemented by a function that returned an `'a * store` value, now we instead use `M.mid` to return an `('a * store) M` value. Where before `mbind` supplied an `'a state` payload `(xx s)` as an argument to a function, now we instead `M.mbind` it to that function.
88
89 Once again, what do you think you'd get if you wrapped StateT monadic packaging around an Identity monad?
90
91
92 We spell out all the common monads, their common dedicated operations (such as `asks`- 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. LINK TODO
93
94 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 `hoist` them into the outer T packaging. Haskell calls this operation `lift`, but we call it `hoist` because the term "lift" is already now too overloaded. The `hoist` operation brings monadic values or functions from a wrapped monad out into the wrapping.
95
96 Here's an example. Suppose `S` is an instance of a State monad:
97
98         # module S = Monad.State(struct type store = int end);;
99
100 and `OS` is a OptionT wrapped around `S`:
101
102         # module OS = Monad.Option.T(S);;
103
104 Then if you want to use an `S`-specific monad like `modify succ` inside `OS`, you'll have to use `OS`'s `hoist` function, like this:
105
106         # OS.(...hoist (S.modify succ) ...)
107
108 Each monad transformer's `hoist` function will be defined differently. They have to obey the following laws:
109
110 *       `Outer.hoist (Inner.mid a) <~~> Outer.mid a`
111 *       `Outer.hoist (Inner.mbind xx k) <~~> Outer.mbind (Outer.hoist xx) (fun x -> Outer.hoist (k x))`
112
113 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(Option) 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 practice. Think of what you have as a ListT(Option); don't worry about whether the underlying implementation is as an `'a list option` or an `'a option list` or as something more complicated.
114
115 (Except for the homework. There we do prompt you to experiment and figure some of these out. But you won't remember them.)
116
117 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:
118
119         't0                  --->  't0 M
120         't1 -> 't0           --->  't1 -> 't0 M
121         ('t1 -> 't0) -> 't0  --->  ('t1 -> 't0 M) -> 't0 M
122
123 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.)
124
125 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.
126
127 Apart from whose interface is outermost, the behavior of a StateT(Option) and a OptionT(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:
128
129         # module OS = Monad.Option.T(S);;
130         # module SO = S.Z(Monad.Option);; (* we use S.Z instead of S.T because Monad.Option has a mzero *)
131         # OS.(run (hoist (S.modify succ) >> mzero >> hoist S.get >>= fun cur -> mid (cur+10) )) 0;;
132         - : int option * S.store = (None, 1)
133         # OS.(run (hoist (S.modify succ) >> mzero >> hoist (S.put 5) )) 0;;
134         - : unit option * S.store = (None, 1)
135
136 Although we have a wrapped `None`, notice that the store (as it was at the point of failure) was still retrievable.
137
138         # SO.(run (modify succ >> mzero >> get >>= fun cur -> mid (cur+10) )) 0;;
139         - : (int * S.store) Monad.Option.result = None
140
141 When Option is on the inside, on the other hand, as in SO, failure means the whole computation has failed, and even the store is no longer available.
142
143 <!--
144         # ES.(run(hoist (S.modify succ) >> throw "bye" >> hoist S.get >>= fun i -> mid (i+10) )) 0;;
145         - : int Failure.error * S.store = (Failure.Error "bye", 1)
146         # SE.(run(modify succ >> hoist (Failure.throw "bye") >> get >>= fun i -> mid (i+10) )) 0;;
147         - : (int * S.store) Failure.result = Failure.Error "bye"
148         # ES.(run_exn(hoist (S.modify succ) >> throw "bye" >> hoist S.get >>= fun i -> mid (i+10) )) 0;;
149         Exception: Failure "bye".
150         # SE.(run_exn(modify succ >> hoist (Failure.throw "bye") >> get >>= fun i -> mid (i+10) )) 0;;
151         Exception: Failure "bye".
152 -->
153
154 Here's an example wrapping Option around List, and vice versa:
155
156         # module LO = Monad.List.T(Monad.Option);;
157         # module OL = Monad.Option.P(Monad.List);; (* we use the `.P` transformer to hoist List's ++ operation *)
158         # OL.(run (mzero ++ mid 20 >>= fun x -> mid (x+10) ));;
159         - : int OL.result = [Some 30]
160
161 When List is on the inside, the failed results just got dropped and the computation proceeds without them.
162
163         # LO.(run (hoist Monad.Option.mzero ++ mid 20 >>= fun x -> mid (x+10) ));;
164         - : int LO.result = None
165
166 On the other hand, when Option is on the inside, as in LO, failures (which we again represent by `mzero`s from the Option monad, not the List monad's own `mzero`; but here since it's the inner monad we need to `hoist Monad.Option.mzero`) abort the whole computation. (If you instead used the List monad's `mzero`, it'd be ignored by `++` and you'd end with just `Some [30]`.)
167
168 This is fun. Here is a List around a List. Notice the difference it makes whether the second `++` is native to the outer `Monad.List`, or whether it's the inner `Monad.List`'s `++` hoisted into the outer wrapper:
169
170         # module LL = Monad.List.T(Monad.List);;
171
172         # LL.(run(mid 1 ++ mid 2 >>= fun x -> mid x ++ mid (10*x) ));;
173         - : int LL.result = \[[1; 10; 2; 20]]
174         #  LL.(run(mid 1 ++ mid 2 >>= fun x -> hoist Monad.List.(mid x ++ mid (10*x)) ));;
175         - : int LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
176
177 <!--
178         # EL.(run((++) (throw "bye") (mid 20) >>= fun i -> mid (i+10)));;
179         - : int EL.result = [Failure.Error "bye"; Failure.Success 30]
180         # LE.(run((++) (hoist (Failure.throw "bye")) (mid 20) >>= fun i -> mid (i+10)));;
181         - : int LE.result = Failure.Error "bye"
182         # EL.(run_exn((++) (throw "bye") (mid 20) >>= fun i -> mid (i+10)));;
183         Exception: Failure "bye".
184         # LE.(run_exn((++) (hoist (Failure.throw "bye")) (mid 20) >>= fun i -> mid (i+10)));;
185         Exception: Failure "bye".
186 -->
187
188
189
190 Further Reading
191 ---------------
192
193 *       This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.cs.virginia.edu/~wh5a/personal/Transformers.pdf)
194 <!-- also http://web.archive.org/web/20140711174905/http://www.grabmueller.de/martin/www/pub/Transformers.pdf -->
195
196 *       Read Part III of [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. Some but not all of this site has been [absorbed into the Haskell wikibook](http://en.wikibooks.org/wiki/Haskell/Monad_transformers).
197