4 * If you've got some block of code that uses `unit`s and `bind`s, and you
5 * want to interpret it alternately using this monad, that monad, or another
6 * monad, you can use OCaml's module system. You'd write your code like this:
9 module Reader_monad = struct
10 (* change this to suit your needs *)
11 type env = int -> int;;
13 type 'a monad = env -> 'a;;
14 let unit a : 'a monad = fun e -> a;;
15 let bind (u : 'a monad) (f : 'a -> 'b monad) : 'b monad =
19 module State_monad = struct
20 (* change this to suit your needs *)
23 type 'a monad = store -> 'a * store;;
24 let unit a : 'a monad = fun s -> (a, s);;
25 let bind (u : 'a monad) (f : 'a -> 'b monad) : 'b monad =
26 fun s -> (let (a, s') = u s in (f a) s');;
29 module List_monad = struct
30 type 'a monad = 'a list;;
31 let unit a : 'a monad = [a];;
32 let bind (u: 'a monad) (f : 'a -> 'b monad) : 'b monad =
33 List.concat(List.map f u);;
37 * Then you can replace code that looks like this:
39 * with code that looks like this:
40 * ... Reader_monad.bind ...
41 * and the latter can be reformulated like this:
42 * let open Reader_monad in ... bind ...
43 * or equivalently, like this:
44 * Reader_monad.(... bind ...)
45 * Then you can use literally the same `... bind ...` code when writing instead:
46 * State_monad.(... bind ...)
49 (* That's great, however it still requires us to repeat the
50 * `... bind ...` code every time we want to change which monad we're working
51 * with. Shouldn't there be a way to _parameterize_ the `... bind ...` code
52 * on a monad, so that we only have to write the `... bind ...` code once,
53 * but can invoke it alternately with the Reader_monad supplied as an
54 * argument, or the State_monad, or another?
56 * There is a way to do this, but it requires putting the `... bind ...` code in
57 * its own module, and making that module parameterized on some X_monad
58 * module. Also we have to explicitly declare what commonality we're expecting
59 * from X_monad modules we're going to use as parameters. We'll explain how to
60 * do this in a moment.
62 * As preparation, a general observation:
63 * 'a and so on are type variables in OCaml; they stand for arbitrary types.
64 * What if you want a variable for a type constructor? For example, you want to
65 * generalize this pattern:
66 * type ('a) t1 = 'a -> ('a) list
67 * type ('a) t2 = 'a -> ('a) option
68 * type ('a) t3 = 'a -> ('a) reader
69 * and so on? OCaml won't let you do this:
70 * type ('a, 'b) t = 'a -> ('a) 'b
71 * To generalize on the 'b position, we instead have to use OCaml's modules,
72 * and in particular its ability to make modules parameterized on other modules
73 * (OCaml calls these parameterized modules Functors, but that name is also
74 * used in other ways in this literature, so I won't give in to it.)
76 * Here's how you'd have to define the t type from above:
78 * (* A sig...end block specifies the type of a module
79 * * What we're doing here is specifying the type of the
80 * * module parameter that will choose
81 * * whether b = list or b = option or b = reader...
82 * * This module parameter may supply values as well as types *)
87 * (* A struct...end block gives a module value
88 * * What we're doing here is building a new module that makes
89 * * use of the module that was supplied as X *)
91 * type ('a) t = 'a -> ('a) X.b
93 * And here's how you'd use it:
94 * module T_list = T_maker(struct type 'a b = 'a list end);;
95 * type 'a t1 = 'a T_list.t;;
96 * module T_option = T_maker(struct type 'a b = 'a option end);;
97 * type 'a t2 = 'a T_option.t;;
100 * I know, it seems unnecessarily complicated. Nonetheless, that's how it
101 * works. And that is also the technique we'll use to make our
102 * `... bind ...` code parametric on some X_monad module.
105 type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);;
113 (Leaf 7, Leaf 11)));;
116 module Tree_monadizer(X : sig
117 (* the module we're using as a parameter has to supply function values
118 * for unit and bind, as well as a monadic type constructor m *)
120 val unit : 'a -> 'a monad
121 val bind : 'a monad -> ('a -> 'b monad) -> 'b monad
123 let rec monadize (f: 'a -> 'b X.monad) (t: 'a tree) : 'b tree X.monad =
125 | Leaf a -> X.bind (f a) (fun b -> X.unit (Leaf b))
127 X.bind (monadize f l) (fun l' ->
128 X.bind (monadize f r) (fun r' ->
129 X.unit (Node (l', r'))))
133 (* Now we supply the Reader monad as a parameter to Tree_monadizer.
134 * We'll get back a module TreeReader that contains a single value,
135 * the monadize function specialized to the Reader monad *)
136 module TreeReader = Tree_monadizer(Reader_monad);;
139 (* Make a TreeState module containing monadize specialized to the State monad *)
140 module TreeState = Tree_monadizer(State_monad);;
143 (* Make a TreeList module containing monadize specialized to the List monad *)
144 module TreeList = Tree_monadizer(List_monad);;
147 (* The Continuation monad is a bit more complicated *)
148 module Continuation_monad = struct
149 type ('a,'r) monad = ('a -> 'r) -> 'r;;
150 let unit a : ('a,'r) monad = fun k -> k a;;
151 let bind (u: ('a,'r) monad) (f: 'a -> ('b,'r) monad) : ('b,'r) monad =
152 fun k -> u (fun a -> f a k);;
155 (* Since the Continuation monad is parameterized on two types---it's
156 * ('a,'r) cont not ('a) cont---we can't match the type ('a) monad that
157 * Tree_monadizer expects in its parameter. So we have to make a different
158 * Tree_monadizer2 that takes a ('a,'z) monad type constructor in its
159 * parameter instead *)
160 module Tree_monadizer2(X : sig
162 val unit : 'a -> ('a,'z) monad
163 val bind : ('a,'z) monad -> ('a -> ('b,'z) monad) -> ('b,'z) monad
165 (* the body of the monadize function is the same; the only difference is in
167 let rec monadize (f: 'a -> ('b,'x) X.monad) (t: 'a tree) : ('b tree,'x) X.monad =
169 | Leaf a -> X.bind (f a) (fun b -> X.unit (Leaf b))
171 X.bind (monadize f l) (fun l' ->
172 X.bind (monadize f r) (fun r' ->
173 X.unit (Node (l', r'))))
176 (* Make a TreeCont module containing monadize specialized to the Cont monad *)
177 module TreeCont = Tree_monadizer2(Continuation_monad);;
182 * Here are all the examples from
183 * http://lambda.jimpryor.net/manipulating_trees_with_monads/
187 let int_readerize : int -> int Reader_monad.monad =
188 fun (a : int) -> fun (env : int -> int) -> env a;;
190 (* int_readerize takes an int and returns a Reader monad that
191 * "looks up" that int in the environment (i.e. modifies it)
192 * this is structurally parallel to the function `lookup` we used
193 * before to "look up" variables in the environment *)
195 (* double each leaf *)
196 let env = fun i -> i + i in
197 TreeReader.monadize int_readerize t1 env;;
199 (* You can also avoid declaring a separate toplevel TreeReader module
200 * (or even a separate Reader_monad module) by ysing one of these forms:
202 * let module T = Tree_monadizer(Reader_monad) in
203 * T.monadize int_readerize t1 env;;
206 * let env = fun i -> i + i in
207 * let module Monad = struct
208 * type env = int -> int;;
209 * type 'a monad = env -> 'a;;
210 * let unit a : 'a monad = fun e -> a;;
211 * let bind (u : 'a monad) (f : 'a -> 'b monad) : 'b monad =
212 * fun e -> f (u e) e;;
214 * let module T = Tree_monadizer(Monad) in
215 * T.monadize int_readerize t1 env;;
218 * let module T = Tree_monadizer(struct
219 * type env = int -> int;;
220 * type 'a monad = env -> 'a;;
221 * let unit a : 'a monad = fun e -> a;;
222 * let bind (u : 'a monad) (f : 'a -> 'b monad) : 'b monad =
223 * fun e -> f (u e) e;;
225 * T.monadize int_readerize t1 env;;
229 (* square each leaf *)
230 let env = fun i -> i * i in
231 TreeReader.monadize int_readerize t1 env;;
235 let incrementer : int -> int State_monad.monad =
236 fun (a : int) -> fun s -> (a, s+1);;
238 (* incrementer takes an 'a and returns it wrapped in a
239 * State monad that increments the store *)
242 let initial_store = 0 in
243 TreeState.monadize incrementer t1 initial_store;;
247 (* replace leaves with list *)
248 TreeList.monadize (fun i -> [ [i;i*i] ]) t1;;
253 let initial_continuation = fun t -> t in
254 TreeCont.monadize Continuation_monad.unit t1 initial_continuation;;
256 (* convert tree to list of leaves *)
257 let initial_continuation = fun t -> [] in
258 TreeCont.monadize (fun a k -> a :: k a) t1 initial_continuation;;
260 (* square each leaf using continuation *)
261 let initial_continuation = fun t -> t in
262 TreeCont.monadize (fun a k -> k (a*a)) t1 initial_continuation;;
264 (* replace leaves with list, using continuation *)
265 let initial_continuation = fun t -> t in
266 TreeCont.monadize (fun a k -> k [a; a*a]) t1 initial_continuation;;
268 (* count leaves, using continuation *)
269 let initial_continuation = fun t -> 0 in
270 TreeCont.monadize (fun a k -> 1 + k a) t1 initial_continuation;;