tweaks

diff --git a/topics/_week9_transformers.mdwn b/topics/_week9_transformers.mdwn
index 414cbb9..24ae852 100644 (file)
--- a/topics/_week9_transformers.mdwn
+++ b/topics/_week9_transformers.mdwn
@@ -4,22 +4,22 @@ So far, we've defined monads as single-layered boxes. In practice, one often wan
 
        type 'a reader =
                env -> 'a;;
 
        type 'a reader =
                env -> 'a;;

-       let mid (a : 'a) : 'a reader =
-               fun e -> a;;
+       let mid (x : 'a) : 'a reader =
+               fun e -> x;;

        let mbind (xx: 'a reader) (k : 'a -> 'b reader) : 'b reader =
                fun e -> (fun x -> k x e) (xx e);;
 
        let mbind (xx: 'a reader) (k : 'a -> 'b reader) : 'b reader =
                fun e -> (fun x -> k x e) (xx e);;
 

-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 any Reader monad is being supplied as an argument to another function. That will help make some patterns that are coming up more salient.
+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.

 
 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?
 
 
 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?
 

-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.bind` to get at *its* wrapped `'a`. This sometimes works.
+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.

 
 

-But there are two problems: (1) It's cumbersome having to work with *both* `reader_mbind` 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* `mbind` that took our `'a M_inside_Reader`, and sequenced it with a single `'a -> 'b M_inside_Reader` function. Similarly for `mid`. This is what the ReaderT monad transformer will let us do.
+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.

 
 (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.
 
 
 (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.
 

-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 `mid` and `mbind`, to define a new monad ReaderT(M) that fuses the behavior of Reader and M.
+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.

 
 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).
 
 
 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).
 


@@ -36,22 +36,22 @@ Here's how it's implemented:
        (* this _happens_ also to be the type of an ('a M) reader
         * but as we noted, you can't rely on that pattern always to hold *)
 
        (* this _happens_ also to be the type of an ('a M) reader
         * but as we noted, you can't rely on that pattern always to hold *)
 

-       let mid (a : 'a) : 'a readerT(M) =
-               fun e -> M.unit a;;
+       let mid (x : 'a) : 'a readerT(M) =
+               fun e -> M.mid x;;

 
        let mbind (xx : 'a readerT(M)) (k : 'a -> 'b readerT(M)) : 'b readerT(M) =
 
        let mbind (xx : 'a readerT(M)) (k : 'a -> 'b readerT(M)) : 'b readerT(M) =

-               fun e -> M.bind (xx e) (fun x -> k x e);;
+               fun e -> M.mbind (xx e) (fun x -> k x e);;

 
 

-Notice the key differences: where before `mid` was implemented by a function that just returned `a`, now we
-instead return `M.unit a`. Where before `mbind` just supplied value `xx e`
-of type `'a reader` as an argument to a function, now we instead
-`M.bind` the corresponding value to the function. Notice also the differences
+Notice the key differences: where before `mid x` was implemented by a function that just returned `x`, now we
+instead return `M.mid x`. Where before `mbind` just supplied the payload `xx e`
+of an `'a reader` as an argument to a function, now we instead
+`M.mbind` the corresponding value to the function. Notice also the differences

 in the types.
 
 What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
 
        type 'a identity = 'a;;
 in the types.
 
 What is the relation between Reader and ReaderT? Well, suppose you started with the Identity monad:
 
        type 'a identity = 'a;;

-       let mid (a : 'a) : 'a = a;;
+       let mid (x : 'a) : 'a = x;;

        let mbind (xx : 'a) (k : 'a -> 'b) : 'b = k xx;;
 
 and you used the ReaderT transformer to wrap the Identity monad inside Readerish packaging. What do you suppose you would get?
        let mbind (xx : 'a) (k : 'a -> 'b) : 'b = k xx;;
 
 and you used the ReaderT transformer to wrap the Identity monad inside Readerish packaging. What do you suppose you would get?


@@ -63,13 +63,13 @@ The relations between the State monad and the StateT monadic transformer are par
        type 'a state =
                store -> ('a * store);;
 
        type 'a state =
                store -> ('a * store);;
 

-       let mid (a : 'a) : 'a state =
-               fun s -> (a, s);;
+       let mid (x : 'a) : 'a state =
+               fun s -> (x, s);;

 
        let mbind (xx : 'a state) (k : 'a -> 'b state) : 'b state =
 
        let mbind (xx : 'a state) (k : 'a -> 'b state) : 'b state =

-               fun s -> (fun (a, s') -> k a s') (xx s);;
+               fun s -> (fun (x, s') -> k x s') (xx s);;

 
 

-We've used `(fun (a, s') -> k a s') (xx s)` instead of the more familiar `let (a, s') = xx s in k 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:
+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:

 
        (* monadic operations for the StateT monadic transformer *)
 
 
        (* monadic operations for the StateT monadic transformer *)
 


@@ -77,41 +77,42 @@ We've used `(fun (a, s') -> k a s') (xx s)` instead of the more familiar `let (a
                store -> ('a * store) M;;
        (* notice this is not an ('a M) state *)
 
                store -> ('a * store) M;;
        (* notice this is not an ('a M) state *)
 

-       let mid (a : 'a) : 'a stateT(M) =
-               fun s -> M.unit (a, s);;
+       let mid (x : 'a) : 'a stateT(M) =
+               fun s -> M.mid (x, s);;

 
        let mbind (xx : 'a stateT(M)) (k : 'a -> 'b stateT(M)) : 'b stateT(M) =
 
        let mbind (xx : 'a stateT(M)) (k : 'a -> 'b stateT(M)) : 'b stateT(M) =

-               fun s -> M.bind (xx s) (fun (a, s') -> k a s');;
+               fun s -> M.mbind (xx s) (fun (x, s') -> k x s');;

 
 
 
 

-Do you see the pattern? Where before `mid` 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 `mbind` supplied an `'a state` value `(xx s)` as an argument to a function, now we instead `M.bind` it to that function.
+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.

 
 Once again, what do you think you'd get if you wrapped StateT monadic packaging around an Identity monad?
 
 
 
 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`- 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.
+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

 
 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.
 
 Here's an example. Suppose `S` is an instance of a State monad:
 
 
 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.
 
 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);;
+       # module S = Monad.State(struct type store = int end);;

 
 

-and `MS` is a MaybeT wrapped around `S`:
+and `OS` is a OptionT wrapped around `S`:

 
 

-       # module MS = Maybe_monad.T(S);;
+       # module OS = Monad.Option.T(S);;

 
 

-Then if you want to use an `S`-specific monad like `modify succ` inside `MS`, you'll have to use `MS`'s `hoist` function, like this:
+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:

 
 

-       # MS.(...hoist (S.modify succ) ...)
+       # OS.(...hoist (S.modify succ) ...)

 
 Each monad transformer's `hoist` function will be defined differently. They have to obey the following laws:
 
 
 Each monad transformer's `hoist` function will be defined differently. They have to obey the following laws:
 

-*      `Outer.hoist (Inner.unit a) <~~> Outer.unit a`
-*      `Outer.hoist (Inner.bind xx k) <~~> Outer.bind (Outer.hoist xx) (fun x -> Outer.hoist (k x))`
+*      `Outer.hoist (Inner.mid a) <~~> Outer.mid a`
+*      `Outer.hoist (Inner.mbind xx k) <~~> Outer.mbind (Outer.hoist xx) (fun x -> Outer.hoist (k x))`

 
 

-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.
+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.
+
+(Except for the homework. There we do prompt you to experiment and figure some of these out. But you won't remember them.)

 
 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:
 
 
 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:
 


@@ -123,21 +124,21 @@ Ken Shan's paper [Monads for natural language semantics](http://arxiv.org/abs/cs
 
 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.
 
 
 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:
+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:

 
 

-       # module MS = Maybe_monad.T(S);;
-       # module SM = S.T(Maybe_monad);;
-       # MS.(run (hoist (S.modify succ) >> zero () >> hoist S.get >>= fun cur -> mid (cur+10) )) 0;;
+       # module OS = Monad.Option.T(S);;
+       # module SO = S.Z(Monad.Option);; (* we use S.Z instead of S.T because Monad.Option has a mzero *)
+       # OS.(run (hoist (S.modify succ) >> mzero >> hoist S.get >>= fun cur -> mid (cur+10) )) 0;;

        - : int option * S.store = (None, 1)
        - : int option * S.store = (None, 1)

-       # MS.(run (hoist (S.modify succ) >> zero () >> hoist (S.put 5) )) 0;;
+       # OS.(run (hoist (S.modify succ) >> mzero >> hoist (S.put 5) )) 0;;

        - : unit option * S.store = (None, 1)
 
        - : unit 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.
+Although we have a wrapped `None`, notice that the store (as it was at the point of failure) was still retrievable.

 
 

-       # SM.(run (modify succ >> hoist (Maybe_monad.zero ()) >> get >>= fun cur -> mid (cur+10) )) 0;;
-       - : (int * S.store) Maybe_monad.result = None
+       # SO.(run (modify succ >> mzero >> get >>= fun cur -> mid (cur+10) )) 0;;
+       - : (int * S.store) Monad.Option.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.
+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.

 
 <!--
        # ES.(run(hoist (S.modify succ) >> throw "bye" >> hoist S.get >>= fun i -> mid (i+10) )) 0;;
 
 <!--
        # ES.(run(hoist (S.modify succ) >> throw "bye" >> hoist S.get >>= fun i -> mid (i+10) )) 0;;


@@ -150,19 +151,22 @@ When Maybe is on the inside, on the other hand, a failure means the whole comput
        Exception: Failure "bye".
 -->
 
        Exception: Failure "bye".
 -->
 

-Here's an example wrapping Maybe around List, and vice versa:
+<!--
+Here's an example wrapping Option around List, and vice versa:

 
 

-       # module LM = List_monad.T(Maybe_monad);;
-       # module ML = Maybe_monad.T(List_monad);;
-       # ML.(run ((++) (zero ()) (mid 20) >>= fun i -> mid (i+10)));;
-       - : int ML.result = [Some 30]
+       # module LO = Monad.List.T(Monad.Option);;
+       # module OL = Monad.Option.T(Monad.List);;
+        # let plus = ???;;
+       # OL.(run (plus mzero mid 20 >>= fun i -> mid (i+10)));;
+       - : int OL.result = [Some 30]

 
 

-When List is on the inside, the failed results just get dropped and the computation proceeds without them.
+When List is on the inside, the failed results just got dropped and the computation proceeds without them.

 
 

-       # LM.(run ((++) (hoist (Maybe_monad.zero ())) (mid 20) >>= fun i -> mid (i+10)));;
-       - : int LM.result = None
+       # LO.(run ((++) (hoist Monad.Option.mzero) (mid 20) >>= fun i -> mid (i+10)));;
+       - : int LO.result = None

 
 

-On the other hand, when Maybe is on the inside, failures abort the whole computation.
+On the other hand, when Option is on the inside, as in LO, failures (which we represent by `mzero`s from the Option monad, here `hoist Monad.Option.mzero`, not the List monad's own `mzero`) abort the whole computation.
+-->

 
 <!--
        # EL.(run((++) (throw "bye") (mid 20) >>= fun i -> mid (i+10)));;
 
 <!--
        # EL.(run((++) (throw "bye") (mid 20) >>= fun i -> mid (i+10)));;


@@ -175,9 +179,9 @@ On the other hand, when Maybe is on the inside, failures abort the whole computa
        Exception: Failure "bye".
 -->
 
        Exception: Failure "bye".
 -->
 

-This is fun. Notice the difference it makes whether the second `++` is native to the outer `List_monad`, or whether it's the inner `List_monad`'s `++` hoisted into the outer wrapper:
+This is fun. 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:

 
 

-       # module LL = List_monad.T(List_monad);;
+       # module LL = Monad.List.T(Monad.List);;

 
        # LL.(run((++) (mid 1) (mid 2) >>= fun i -> (++) (mid i) (mid (10*i)) ));;
        - : int LL.result = \[[1; 10; 2; 20]]
 
        # LL.(run((++) (mid 1) (mid 2) >>= fun i -> (++) (mid i) (mid (10*i)) ));;
        - : int LL.result = \[[1; 10; 2; 20]]