From 6620761d57706f681ccf431c19d6d6fd77fa2942 Mon Sep 17 00:00:00 2001
From: Jim Pryor
Date: Sun, 12 Dec 2010 21:00:05 0500
Subject: [PATCH] Expand monad_transformers re elevate, layering
Signedoffby: Jim Pryor

code/monads.ml  28 +
monad_transformers.mdwn  88 ++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 81 insertions(+), 35 deletions()
diff git a/code/monads.ml b/code/monads.ml
index e48fd8d0..b678a92c 100644
 a/code/monads.ml
+++ b/code/monads.ml
@@ 415,13 +415,6 @@ end = struct
end
end
(*
# LL.(run(plus (unit 1) (unit 2) >>= fun i > plus (unit i) (unit(10*i)) ));;
 : ('_a, int) LL.result = [[1; 10; 2; 20]]
# LL.(run(plus (unit 1) (unit 2) >>= fun i > elevate L.(plus (unit i) (unit(10*i)) )));;
 : ('_a, int) LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
*)

(* must be parameterized on (struct type err = ... end) *)
module Error_monad(Err : sig
@@ 516,26 +509,6 @@ module Failure = Error_monad(struct
*)
end)
(*
# EL.(run( plus (throw "bye") (unit 20) >>= fun i > unit(i+10)));;
 : int EL.result = [Failure.Error "bye"; Failure.Success 30]
# LE.(run( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i > unit(i+10)));;
 : int LE.result = Failure.Error "bye"
# EL.(run_exn( plus (throw "bye") (unit 20) >>= fun i > unit(i+10)));;
Exception: Failure "bye".
# LE.(run_exn( plus (elevate (Failure.throw "bye")) (unit 20) >>= fun i > unit(i+10)));;
Exception: Failure "bye".

# ES.(run( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i > unit(i+10) )) 0;;
 : int Failure.error * S.store = (Failure.Error "bye", 1)
# SE.(run( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i > unit(i+10) )) 0;;
 : (int * S.store) Failure.result = Failure.Error "bye"
# ES.(run_exn( elevate (S.puts succ) >> throw "bye" >> elevate S.get >>= fun i > unit(i+10) )) 0;;
Exception: Failure "bye".
# SE.(run_exn( puts succ >> elevate (Failure.throw "bye") >> get >>= fun i > unit(i+10) )) 0;;
Exception: Failure "bye".
 *)

(* must be parameterized on (struct type env = ... end) *)
module Reader_monad(Env : sig type env end) : sig
@@ 667,6 +640,7 @@ end = struct
end
end
+
(* State monad with different interface (structured store) *)
module Ref_monad(V : sig
type value
diff git a/monad_transformers.mdwn b/monad_transformers.mdwn
index 53a16899..ebe9b0c1 100644
 a/monad_transformers.mdwn
+++ b/monad_transformers.mdwn
@@ 12,9 +12,9 @@ So far, we've defined monads as singlelayered boxes. Though in the Groenendijk,
let unit (a : 'a) : 'a reader =
fun e > a;;
let bind (u: 'a reader) (f : 'a > 'b reader) : 'b reader =
 fun e > (fun v > f v e) (u e);;
+ fun e > (fun a > f a e) (u e);;
We've just betaexpanded the familiar `f (u e) e` into `(fun v > f v
+We've just betaexpanded the familiar `f (u e) e` into `(fun a > f a
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.
@@ 50,7 +50,7 @@ Here's how it's implemented:
fun e > M.unit a;;
let bind (u : 'a readerT(M)) (f : 'a > 'b readerT(M)) : 'b readerT(M) =
 fun e > M.bind (u e) (fun v > f v e);;
+ fun e > M.bind (u e) (fun a > f a e);;
Notice the key differences: where before `unit` was implemented by a function that just returned `a`, now we
instead return `M.unit a`. Where before `bind` just supplied value `u e`
@@ 99,9 +99,23 @@ Do you see the pattern? Where before `unit` was implemented by a function that r
Once again, what do you think you'd get if you wrapped StateT monadic packaging around an 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 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.
+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.
+
+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 nonmonadic operations into a monad; `elevate` brings monadic operations from a wrapped monad out into the wrapping.
+
+Here's an example. Suppose `S` is an instance of a State monad:
+
+ # #use "path/to/monads.ml";;
+ # module S = State_monad(struct type store = int end);;
+
+and `MS` is a MaybeT wrapped around `S`:
+
+ # module MS = Maybe_monad.T(S);;
+
+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:
+
+ # MS.(...elevate (S.puts succ) ...)
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 need to use T's `elevate` function on them. This brings the Mbased operation into the TaroundM monadic bundle. Haskell calls this `lift` (MORE...)
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 counterintuitive. 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.
@@ 111,11 +125,69 @@ Notice from the code for StateT, above, that an `'a stateT(M)` is not an `('a M)
't1 > 't0 > 't1 > 't0 M
('t1 > 't0) > 't0 > ('t1 > 't0 M) > 't0 M
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 that form; List for example doesn't.)
+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.)
+
+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.
+
+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:
+
+ # module MS = Maybe_monad.T(S);;
+ # module SM = S.T(Maybe_monad);;
+ # MS.(run (elevate (S.puts succ) >> zero () >> elevate S.get >>= fun cur > unit (cur+10) )) 0;;
+  : int option * S.store = (None, 1)
+
+Although we have a wrapped `None`, notice that the store (as it was at the point of failure) is still retrievable.
+
+ # SM.(run (puts succ >> elevate (Maybe_monad.zero ()) >> get >>= fun cur > unit (cur+10) )) 0;;
+  : ('a, int * S.store) Maybe_monad.result = None
+
+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.
+
+
+
+Here's an example wrapping List around Maybe, and vice versa:
+
+ # module LM = List_monad.T(Maybe_monad);;
+ # module ML = Maybe_monad.T(List_monad);;
+ # ML.(run (plus (zero ()) (unit 20) >>= fun i > unit (i+10)));;
+  : ('_a, int) ML.result = [Some 30]
+
+When List is on the inside, the failed results just get dropped and the computation proceeds without them.
+
+ # LM.(run (plus (elevate (Maybe_monad.zero ())) (unit 20) >>= fun i > unit (i+10)));;
+  : ('_a, int) LM.result = None
+
+On the other hand, when Maybe is on the inside, failures abort the whole computation.
+
+
+
+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:
+
+ # module LL = List_monad.T(List_monad);;
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.
+ # LL.(run(plus (unit 1) (unit 2) >>= fun i > plus (unit i) (unit(10*i)) ));;
+  : ('_a, int) LL.result = [[1; 10; 2; 20]]
+ # LL.(run(plus (unit 1) (unit 2) >>= fun i > elevate L.(plus (unit i) (unit(10*i)) )));;
+  : ('_a, int) LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
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. (MORE...)
Further Reading

2.11.0