tree that is ready to accept any `int -> int` function and produce the
updated tree.
-\tree (. (. (f 2) (f 3)) (. (f 5) (. (f 7) (f 11))))
-
\f .
_____|____
| |
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' ->
+ | Node (l, r) -> state_bind (tree_monadize f r) (fun r' -> (* R first *)
+ state_bind (tree_monadize f l) (fun l'-> (* Then L *)
state_unit (Node (l', r'))));;
# tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
resulting from `bind u f` is a tree with the same strucure as `u`,
except that each leaf `a` has been replaced with `f a`:
-\tree (. (f a1) (. (. (. (f a2) (f a3)) (f a4)) (f a5)))
-
. .
__|__ __|__
| | | |
we'll give an example that will show how an inductive proof would
proceed. Let `f a = Node (Leaf a, Leaf a)`. Then
-\tree (. (. (. (. (a1) (a2)))))
-\tree (. (. (. (. (a1) (a1)) (. (a1) (a1)))))
-
.
____|____
. . | |