tweak monads-lib, start T2
[lambda.git] / monad_transformers.mdwn
1
2 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:
3
4         (* monadic operations for the Reader monad *)
5
6         type 'a reader =
7                 env -> 'a;;
8         let unit (a : 'a) : 'a reader =
9                 fun e -> a;;
10         let bind (u: 'a reader) (f : 'a -> 'b reader) : 'b reader =
11                 fun e -> (fun v -> f v e) (u e);;
12
13 We've just beta-expanded the familiar `f (u e) e` into `(fun v -> f v
14 e) (u e)`. We did that so as to factor out the parts where any Reader monad is
15 being supplied as an argument to another function. That will help make some patterns that are coming up more salient.
16
17 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?
18
19 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."
20
21 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.
22
23 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:
24
25         (* monadic operations for the ReaderT monadic transformer *)
26
27         (* We're not giving valid OCaml code, but rather something
28          * that's conceptually easier to digest.
29          * How you really need to write this in OCaml is more circuitous...
30          * see http://lambda.jimpryor.net/code/tree_monadize.ml for some details. *)
31
32         type (M, 'a) readerT =
33                 env -> 'a M;;
34         (* this happens also to be the type of an ('a M) reader; but don't rely on that pattern to generalize *)
35
36         let unit (a : 'a) : (M, 'a) readerT =
37                 fun e -> M.unit a;;
38
39         let bind (u : (M, 'a) readerT) (f : 'a -> (M, 'b) readerT) : (M, 'b) readerT =
40                 fun e -> M.bind (u e) (fun v -> f v e);;
41
42 Notice the key differences: where before we just returned `a`, now we
43 instead return `M.unit a`. Where before we just supplied value `u e`
44 of type `'a reader` as an argument to a function, now we instead
45 `M.bind` the `'a reader` to that function. Notice also the differences
46 in the types.
47
48 What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
49
50         type 'a identity = 'a;;
51         let unit (a : 'a) : 'a = a;;
52         let bind (u : 'a) (f : 'a -> 'b) : 'b = f u;;
53
54 and you used the ReaderT transformer to wrap the Identity monad inside Reader packaging. What do you suppose you would get?
55
56 The relations between the State monad and the StateT monadic transformer are parallel:
57
58         (* monadic operations for the State monad *)
59
60         type 'a state =
61                 store -> ('a * store);;
62
63         let unit (a : 'a) : 'a state =
64                 fun s -> (a, s);;
65
66         let bind (u : 'a state) (f : 'a -> 'b state) : 'b state =
67                 fun s -> (fun (a, s') -> f a s') (u s);;
68
69 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:
70
71         (* monadic operations for the StateT monadic transformer *)
72
73         type (M, 'a) stateT =
74                 store -> ('a * store) M;;
75         (* notice this is not an ('a M) state *)
76
77         let unit (a : 'a) : (M, 'a) stateT =
78                 fun s -> M.unit (a, s);;
79
80         let bind (u : (M, 'a) stateT) (f : 'a -> (M, 'b) stateT) : (M, 'b) stateT =
81                 fun s -> M.bind (u s) (fun (a, s') -> f a s');;
82
83
84 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.
85
86 Once again, what do you think you'd get if you wrapped a StateT monadic box around an Identity monad?
87
88 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:
89
90         't0                  --->  't0 M
91         't1 -> 't0           --->  't1 -> 't0 M
92         ('t1 -> 't0) -> 't0  --->  ('t1 -> 't0 M) -> 't0 M
93
94 Here's how this works for List and ListT:
95
96         (* monadic operations for the List monad *)
97
98         (* type 'a list is already pre-defined *)
99
100         let unit (a : 'a) : 'a list =
101                 [a];;
102
103         let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
104                 (fun v -> List.concat (List.map f v)) u
105
106         (* monadic operations for the ListT monadic transformer *)
107
108         type ('a, M) listT =
109                 'a list M;;
110
111         let unit (a : 'a) : 'a list =
112                 [a];;
113
114         let bind (u : 'a list) (f : 'a -> 'b list) : 'b list =
115                 (fun v -> List.concat (List.map f v)) u
116
117
118 Some comments before we proceed:
119
120 *       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.)
121 *       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.
122 *       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]].
123
124
125 <!--
126 This module is inspired by the paper Functional Programming with Overloading and Higher-Order Polymorphism, Mark P Jones (http://www.cse.ogi.edu/~mpj/) Advanced School of Functional Programming, 1995.
127 http://web.cecs.pdx.edu/~mpj/pubs/springschool.html
128 Mark Jones' influential paper that inspired the Haskell monad template library. 
129 -->
130
131
132 Okay, now let's do the same thing for our Tree monad.
133
134         (* monadic operations for the Tree monad *)
135
136         type 'a tree =
137                 Leaf of 'a | Node of ('a tree) * ('a tree);;
138
139         let unit (a: 'a) : 'a tree =
140                 Leaf a;;
141
142         let rec bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
143             match u with
144             | Leaf a -> f a;;
145             | Node (l, r) -> (fun l' r' -> Node (l', r')) (bind l f) (bind r f);;
146
147         (* monadic operations for the TreeT monadic transformer *)
148         (* NOTE THIS IS NOT YET WORKING --- STILL REFINING *)
149
150         type (M, 'a) treeT =
151                 'a tree M;;
152
153         let unit (a: 'a) : (M, 'a) tree =
154                 M.unit (Leaf a);;
155
156         let rec bind (u : (M, 'a) tree) (f : 'a -> (M, 'b) tree) : (M, 'b) tree =
157             match u with
158             | Leaf a -> M.bind (f a) (fun b -> M.unit (Leaf b))
159             | Node (l, r) -> M.bind (bind l f) (fun l' ->
160                                                         M.bind (bind r f) (fun r' ->
161                                                                 M.unit (Node (l', r'));;
162
163         (* 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. *)
164
165 Compare this definition of `bind` for the TreeT monadic transformer to our earlier definition of `tree_monadize`, specialized for the Reader monad:
166
167         let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
168             match t with
169             | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
170             | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
171                                reader_bind (tree_monadize f r) (fun r' ->
172                                  reader_unit (Node (l', r'))));;
173
174
175 *       This is excellent, everyone should read: [Monad Transformers Step by Step](http://www.grabmueller.de/martin/www/pub/Transformers.pdf)
176 *       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).
177