transformers tweak
[lambda.git] / monad_transformers.mdwn
index 57affe5..086a2ff 100644 (file)
@@ -116,6 +116,10 @@ Then if you want to use an `S`-specific monad like `puts succ` inside `MS`, you'
 
        # MS.(...elevate (S.puts succ) ...)
 
+Each monad transformer's `elevate` function will be defined differently. They have to obey the following laws:
+
+*      `Outer.elevate (Inner.unit a) <~~> Outer.unit a`
+*      `Outer.elevate (Inner.bind u f) <~~> Outer.bind (Outer.elevate u) (fun a -> Outer.elevate (f a))`
 
 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.
 
@@ -135,6 +139,8 @@ Apart from whose interface is outermost, the behavior of a StateT(Maybe) and a M
        # 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)
+       # MS.(run (elevate (S.puts succ) >> zero () >> elevate (S.put 5) )) 0;;
+       - : 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.
 
@@ -154,7 +160,7 @@ When Maybe is on the inside, on the other hand, a failure means the whole comput
        Exception: Failure "bye".
 -->
 
-Here's an example wrapping List around Maybe, and vice versa:
+Here's an example wrapping Maybe around List, and vice versa:
 
        # module LM = List_monad.T(Maybe_monad);;
        # module ML = Maybe_monad.T(List_monad);;
@@ -186,7 +192,7 @@ This is fun. Notice the difference it makes whether the second `plus` is native
        # 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]]
+       - : ('_a, int) LL.result = [[1; 2]; [1; 20]; [10; 2]; [10; 20]]
 
 
 
@@ -246,7 +252,7 @@ then `list_bind u f` would be `concat [[]; [2]; [2; 4]; [2; 4; 8]]`, that is `[2
                                 |  |
                                 4  8
 
-Except, as we mentioned, our implementation of the Tree monad incorporates an Optionish layer too. So `f' 2` should be not `Leaf 2` but `Some (Leaf 2)`. What if `f'` also mapped `1` to `None` and `4` to `Some (Node (Leaf 2, Leaf 4))`. Then binding the tree `Node (Leaf 1, Node (Leaf 2, Leaf 4))` to `f'` would delete thr branch corresponding to the original `Leaf 1`, and would splice in the results for `f' 2` and `f' 4`, yielding:
+Except, as we mentioned, our implementation of the Tree monad incorporates an Optionish layer too. So `f' 2` should be not `Leaf 2` but `Some (Leaf 2)`. What if `f'` also mapped `1` to `None` and `4` to `Some (Node (Leaf 2, Leaf 4))`. Then binding the tree `Node (Leaf 1, Node (Leaf 2, Leaf 4))` (really the tree itself needs to be wrapped in a `Some`, too, but let me neglect that) to `f'` would delete the branch corresponding to the original `Leaf 1`, and would splice in the results for `f' 2` and `f' 4`, yielding:
 
         .                        
        _|__  >>=  f' ~~>         
@@ -281,15 +287,203 @@ You have to instead say something like this:
 How is all this related to our tree\_monadize function?
 -------------------------------------------------------
 
+Our Tree monad has a corresponding TreeT transformer. Simplified, its implementation looks something like this (we apply it to an inner Reader monad):
+
+
+       type 'a tree_reader = 'a tree reader;;
+       (* really it's an 'a tree option reader, but as I said we're simplifying *)
+
+       let tree_reader_unit (a:'a) : 'a tree_reader = reader_unit (Leaf a);;
+
+       let tree_reader_bind (u: 'a tree_reader) (f: 'a -> 'b tree_reader) : 'b tree_reader =
+         reader_bind u (fun us ->
+               let rec loop us = match us with
+                 | Leaf a ->
+                 f a
+                 | Node(l,r) ->
+                         reader_bind (loop l) (fun ls ->
+                               reader_bind (loop r) (fun rs ->
+                                 reader_unit (Node(ls, rs))))
+               in loop us);;
+
+       let tree_reader_elevate (inner : 'a reader) : 'a tree_reader =
+               reader_bind inner (fun a -> reader_unit (Leaf a))
+
 Recall our earlier definition of `tree_monadize`, specialized for the Reader monad:
 
        let rec tree_monadize (f : 'a -> 'b reader) (t : 'a tree) : 'b tree reader =
            match t with
-           | Leaf a -> reader_bind (f a) (fun b -> reader_unit (Leaf b))
-           | Node (l, r) -> reader_bind (tree_monadize f l) (fun l' ->
-                              reader_bind (tree_monadize f r) (fun r' ->
-                                reader_unit (Node (l', r'))));;
+           | Leaf a ->
+                       (* the next line is equivalent to: tree_reader_elevate (f a) *)
+               reader_bind (f a) (fun b -> reader_unit (Leaf b))
+           | Node (l, r) ->
+               reader_bind (tree_monadize f l) (fun ls ->
+                 reader_bind (tree_monadize f r) (fun rs ->
+                   reader_unit (Node (ls, rs))));;
+
+We rendered the result type here as `'b tree reader`, as we did in our earlier discussion, but as we can see from the above implementation of TreeT(Reader), that's the type of an `'b tree_reader`, that is, of a layered box consisting of TreeT packaging wrapped around an inner Reader box.
+
+The definitions of `tree_monadize` and `tree_reader_bind` should look very similar. They're not quite the same. There's the difference in the order of their function-like and tree-like arguments, but that's inconsequential. More important is that the types of their arguments differs. `tree_reader_bind` wants a tree that's already fused with a reader; `tree_monadize` instead just wants a plain tree. `tree_reader_bind` wants a function that takes the elements occupying its leaves into other `tree_reader`s; `tree_monadize` just wants it to take them into plain `reader`s. That's why the application of `f` to `a` has to be `elevate`d in the `tree_monadize` clause for `Leaf a -> ...`.
+
+But there is an obvious common structure to these two functions, and indeed in the [[monad library]] their more complicated cousins are defined in terms of common pieces. In the monad library, the `tree_monadize` function is called `distribute`; this is an operation living inside the TreeT packaging. There's an analogous `distribute` function living inside the ListT packaging. (Haskell has the second but not the first; it calls it `mapM` and it lives inside the wrapped base monad, instead of the List packaging.)
+
+We linked to [some code](/code/tree_monadize.ml) earlier that demonstrated all the `tree_monadize` examples in a compact way.
+
+Here's how to demonstrate the same examples, using the monad library. First, preliminaries:
+
+       # #use "path/to/monads.ml";;
+       # module T = Tree_monad;;
+       # module R = Reader_monad(struct type env = int -> int end);;
+       # module S = State_monad(struct type store = int end);;
+       # module L = List_monad;;
+       # module C = Continuation_monad;;
+       # module TR = T.T(R);;
+       # module TS = T.T(S);;
+       # module TL = T.T(L);;
+       # module TC = T.T(C);;
+       # let t1 = Some (T.Node (T.Node (T.Leaf 2, T.Leaf 3), T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))));;
+
+We can use TreeT(Reader) to modify leaves:
+
+       # let tree_reader = TR.distribute (fun i -> R.asks (fun e -> e i)) t1;;
+       # TR.run tree_reader (fun i -> i+i);;
+       (*
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 4, T.Leaf 6),
+               T.Node (T.Leaf 10, T.Node (T.Leaf 14, T.Leaf 22))))
+       *)
+
+Here's a comparison of how distribute works for trees and how it works for lists:
+
+       # module LR = L.T(R);;
+       # let l1 = [2; 3; 5; 7; 11];;
+       # LR.(run (distribute (fun i -> R.(asks (fun e -> e i))) l1)) (fun i -> i+i);;
+       - : int list = [4; 6; 10; 14; 22]
+
+<!--
+More complex: here we use the monadic `list_reader` or `tree_reader` we got back from `distribute` and `bind` it to other operations:
+
+       # let u = LR.distribute (fun i -> R.(asks (fun e -> e i))) l1 in
+         LR.(run(u >>= fun i -> plus (unit i) (unit (10*i)))) (fun i -> i + i);;
+       - : int list = [4; 40; 6; 60; 10; 100; 14; 140; 22; 220]
+       # let v = TR.distribute (fun i -> R.(asks (fun e -> e i))) t1 in
+         TR.(run(v >>= fun i -> plus (unit i) (unit (10*i)))) (fun i -> i + i);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Node (T.Leaf 4, T.Leaf 40), T.Node (T.Leaf 6, T.Leaf 60)),
+               T.Node
+                (T.Node (T.Leaf 10, T.Leaf 100),
+                 T.Node (T.Node (T.Leaf 14, T.Leaf 140), T.Node (T.Leaf 22, T.Leaf 220)))))
+-->
+
+We can use TreeT(State) to count leaves:
+
+       # let tree_counter = TS.distribute (fun i -> S.(puts succ >> unit i)) t1 in
+         TS.run tree_counter 0;;
+       (*
+       - : int T.tree option * S.store =
+       (Some
+         (T.Node
+               (T.Node (T.Leaf 2, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11)))),
+        5)
+       *)
+
+or to annotate leaves:
+
+       # let tree_annotater = TS.distribute (fun i -> S.(puts succ >> get >>= fun s -> unit (i,s))) t1 in
+         TS.run tree_annotater 0;;
+       - : (int * S.store) T.tree option * S.store =
+       (Some
+         (T.Node
+               (T.Node (T.Leaf (2, 1), T.Leaf (3, 2)),
+                T.Node (T.Leaf (5, 3), T.Node (T.Leaf (7, 4), T.Leaf (11, 5))))),
+        5)
+
+Here's a comparison of how distribute works for trees and how it works for lists:
+
+       # module LS = L.T(S);;
+
+       # let list_counter = LS.distribute (fun i -> S.(puts succ >> unit i)) l1 in
+         LS.run list_counter 0;;
+       - : int list * S.store = ([2; 3; 5; 7; 11], 5)
+
+       # let list_annotater = LS.distribute (fun i -> S.(puts succ >> get >>= fun s -> unit (i,s) )) l1 in
+         LS.run list_annotater 0;;
+       - : (int * S.store) list * S.store =
+       ([(2, 1); (3, 2); (5, 3); (7, 4); (11, 5)], 5)
+
+
+<!--
+#   let u = LS.distribute (fun i -> if i = -1 then S.get else if i < 0 then S.(puts     succ >> unit 0) else S.unit i) [10;-1;-2;-1;20] in
+  LS.run u 0;;
+- : S.store list * S.store = ([10; 0; 0; 1; 20], 1)
+-->
+
+
+We can use TreeT(List) to copy the tree with different choices for some of the leaves:
+
+       # let tree_chooser = TL.distribute (fun i -> L.(if i = 2 then plus (unit 20) (unit 21) else unit i)) t1;;
+       # TL.run tree_chooser;;
+       - : ('_a, int) TL.result =
+       [Some
+         (T.Node
+               (T.Node (T.Leaf 20, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))));
+        Some
+         (T.Node
+               (T.Node (T.Leaf 21, T.Leaf 3),
+                T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))))]
+
+
+Finally, we use TreeT(Continuation) to do various things. For reasons I won't explain here, the library currently requires you to run the Tree-plus-Continuation bundle using a different sequence of `run` commands:
+
+We can do nothing:
+<!--
+let initial_continuation = fun t -> t in
+TreeCont.monadize Continuation_monad.unit t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.unit t1)) (fun t -> t);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 2, T.Leaf 3),
+               T.Node (T.Leaf 5, T.Node (T.Leaf 7, T.Leaf 11))))
+
+We can square each leaf. The meaning of `shift` will be explained in [[CPS and Continuation Operators]].
+<!--
+let initial_continuation = fun t -> t in
+TreeCont.monadize (fun a k -> k (a*a)) t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k (a*a))) t1)) (fun t -> t);;
+       - : int T.tree option =
+       Some
+        (T.Node
+          (T.Node (T.Leaf 4, T.Leaf 9),
+               T.Node (T.Leaf 25, T.Node (T.Leaf 49, T.Leaf 121))))
+
+We can count the leaves:
+<!--
+let initial_continuation = fun t -> 0 in
+TreeCont.monadize (fun a k -> 1 + k a) t1 initial_continuation;;
+-->
+
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k a >>= fun v -> unit (1+v))) t1)) (fun t -> 0);;
+       - : int = 5
+
+
+We can convert the tree to a list of leaves:
+<!--
+let initial_continuation = fun t -> [] in
+TreeCont.monadize (fun a k -> a :: k a) t1 initial_continuation;;
+-->
 
+       # C.run_exn TC.(run (distribute C.(fun a -> shift (fun k -> k a >>= fun v -> unit (a::v))) t1)) (fun t -> []);;
+       - : int list = [2; 3; 5; 7; 11]
 
-(MORE...)