-
-Tree Monads
-===========
-
-Our [[monad library]] includes a `Tree_monad`, for binary, leaf-labeled trees. There are other kinds of trees you might want to monadize, but we took the name `Tree_monad` for this one. Like the Haskell [SearchTree](http://hackage.haskell.org/packages/archive/tree-monad/0.2.1/doc/html/src/Control-Monad-SearchTree.html#SearchTree) monad, our `Tree_monad` also incorporates an Optionish layer. (See the comments in our library code about `plus` and `zero` for discussion of why.)
-
-So how does our `Tree_monad` behave? Simplified, its implementation looks something like this:
-
- (* monadic operations for the Tree monad *)
-
- type 'a tree =
- Leaf of 'a | Node of ('a tree) * ('a tree);;
-
- let unit (a: 'a) : 'a tree =
- Leaf a;;
-
- let rec bind (u : 'a tree) (f : 'a -> 'b tree) : 'b tree =
- match u with
- | Leaf a -> f a;;
- | Node (l, r) ->
- let l' = bind l f in
- let r' = bind r f in
- Node (l', r')
-
-Recall how `bind` works for the List monad. If you have a list:
-
- let u = [1; 2; 4; 8];;
-
-and a function `f` such that:
-
- f 1 ~~> []
- f 2 ~~> [2]
- f 4 ~~> [2; 4]
- f 8 ~~> [2; 4; 8]
-
-then `list_bind u f` would be `concat [[]; [2]; [2; 4]; [2; 4; 8]]`, that is `[2; 2; 4; 2; 4; 8]`. It splices the lists returned by `f` into the corresponding positions in the original list structure. The `tree_bind` operation works the same way. If `f'` maps `2` to the tree `Leaf 2` and `8` to the tree `Node (Leaf 2, Node (Leaf 4, Leaf 8))`, then binding the tree `u` to `f'` will splice the trees returned by `f'` to the corresponding positions in the original structure:
-
- u
- . .
- _|__ >>= f' ~~> _|__
- | | | |
- 2 8 2 .
- _|__
- | |
- 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))` (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' ~~>
- | |
- 1 . .
- _|__ _|__
- | | | |
- 2 4 2 .
- _|__
- | |
- 2 4
-
-As always, the functions you bind an `'a tree` to need not map `'a`s to `'a tree`s; they can map them to `'b tree`s instead. For instance, we could transform `Node (Leaf 1, Node (Leaf 2, Leaf 4))` instead into `Node (Leaf "two", Node (Leaf "two", Leaf "four"))`.
-
-As we [mention in the notes](/monad_library), our monad library encapsulates the implementation of its monadic types. So to work with it you have to use the primitives it provides. You can't say:
-
- # Tree_monad.(orig_tree >>= fun a -> match a with
- | 4 -> Some (Node (Leaf 2, Leaf 4))
- | _ -> None);;
- Error: This expression has type int Tree_monad.tree option
- but an expression was expected of type ('a, 'b) Tree_monad.m
-
-You have to instead say something like this:
-
- # Tree_monad.(orig_tree >>= fun a -> match a with
- | 4 -> plus (unit 2) (unit 4)
- | _ -> zero () );;
- - : ('_a, int) Tree_monad.m = <abstr>
-
-
-
-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 ->
- (* 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:
-<!--
-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))))
-
-The meaning of `shift` will be explained in [[CPS and Continuation Operators]]. Here you should just regard it as a primitive operation in our Continuation monad. In [this code](/code/tree_monadize.ml) you could simply write:
-
- TreeCont.monadize (fun a -> fun k -> k (a*a)) t1 (fun t -> t);;
-
-But because of the way our monad library hides the underlying machinery, here you can no longer just say `fun k -> k (a*a)`; you have to say `shift (fun k -> k (a*a))`.
-
-Moving on, 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
-
-
-And 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]
-
-