-`reader` with `state`:
-
-<pre>
-let rec treemonadizer (f:'a -> 'b state) (t:'a tree):('b tree) state =
- match t with Leaf x -> state_bind (f x) (fun x' -> state_unit (Leaf x'))
- | Node (l, r) -> state_bind (treemonadizer f l) (fun x ->
- state_bind (treemonadizer f r) (fun y ->
- state_unit (Node (x, y))));;
-</pre>
-
-Then we can count the number of nodes in the tree:
-
-<pre>
-# treemonadizer state_unit t1 0;;
-- : int tree * int =
-(Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 13)
-
- .
- ___|___
- | |
- . .
-_|__ _|__
-| | | |
-2 3 5 .
- _|__
- | |
- 7 11
-</pre>
-
-Notice that we've counted each internal node twice---it's a good
-exercise to adjust the code to count each node once.
+`'b reader` with `'b state`, and substituting in the appropriate unit and bind:
+
+ let rec tree_monadize (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+ match t with
+ | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+ | Node (l, r) -> state_bind (tree_monadize f l) (fun l' ->
+ state_bind (tree_monadize f r) (fun r' ->
+ state_unit (Node (l', r'))));;
+
+Then we can count the number of leaves in the tree:
+
+ # tree_monadize (fun a -> fun s -> (a, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 5)
+
+ .
+ ___|___
+ | |
+ . .
+ _|__ _|__ , 5
+ | | | |
+ 2 3 5 .
+ _|__
+ | |
+ 7 11
+
+Note that the value returned is a pair consisting of a tree and an
+integer, 5, which represents the count of the leaves in the tree.
+
+Why does this work? Because the operation `fun a -> fun s -> (a, s+1)`
+takes an `int` and wraps it in an `int state` monadic box that
+increments the state. When we give that same operations to our
+`tree_monadize` function, it then wraps an `int tree` in a box, one
+that does the same state-incrementing for each of its leaves.
+
+We can use the state monad to replace leaves with a number
+corresponding to that leave's ordinal position. When we do so, we
+reveal the order in which the monadic tree forces evaluation:
+
+ # tree_monadize (fun a -> fun s -> (s+1, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)
+
+The key thing to notice is that instead of copying `a` into the
+monadic box, we throw away the `a` and put a copy of the state in
+instead.
+
+Reversing the order requires reversing the order of the state_bind
+operations. It's not obvious that this will type correctly, so think
+it through:
+
+ let rec tree_monadize_rev (f : 'a -> 'b state) (t : 'a tree) : 'b tree state =
+ match t with
+ | Leaf a -> state_bind (f a) (fun b -> state_unit (Leaf b))
+ | Node (l, r) -> state_bind (tree_monadize f r) (fun r' ->
+ state_bind (tree_monadize f l) (fun l' ->
+ state_unit (Node (l', r'))));;
+
+ # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
+ - : int tree * int =
+ (Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)
+
+We will need below to depend on controlling the order in which nodes
+are visited when we use the continuation monad to solve the
+same-fringe problem.