XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=manipulating_trees_with_monads.mdwn;h=0d9e33df3425822ec12e1b4b8aab11fa2594475c;hp=609443f6c58367d1aa5ea36276b5407502abfcfe;hb=148ffe89f0869ef1e94733dd1fb0efb16f9f34ed;hpb=411e4238d1a711d78dac9b529a07c3ca554829c7
diff git a/manipulating_trees_with_monads.mdwn b/manipulating_trees_with_monads.mdwn
index 609443f6..0d9e33df 100644
 a/manipulating_trees_with_monads.mdwn
+++ b/manipulating_trees_with_monads.mdwn
@@ 46,18 +46,18 @@ We'll be using trees where the nodes are integers, e.g.,
Our first task will be to replace each leaf with its double:
 let rec tree_map (t : 'a tree) (leaf_modifier : 'a > 'b): 'b tree =
+ let rec tree_map (leaf_modifier : 'a > 'b) (t : 'a tree) : 'b tree =
match t with
 Leaf i > Leaf (leaf_modifier i)
  Node (l, r) > Node (tree_map l leaf_modifier,
 tree_map r leaf_modifier);;
+  Node (l, r) > Node (tree_map leaf_modifier l,
+ tree_map leaf_modifier r);;
`tree_map` takes a tree and a function that transforms old leaves into
new leaves, and maps that function over all the leaves in the tree,
leaving the structure of the tree unchanged. For instance:
let double i = i + i;;
 tree_map t1 double;;
+ tree_map double t1;;
 : int tree =
Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))
@@ 80,7 +80,7 @@ each leaf instead, by supplying the appropriate `int > int` operation
in place of `double`:
let square i = i * i;;
 tree_map t1 square;;
+ tree_map square t1;;
 : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))
@@ 140,7 +140,7 @@ It would be a simple matter to turn an *integer* into an `int reader`:
asker 2 (fun i > i + i);;
 : int = 4
This is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to.
+`asker a` is a monadic box that waits for an an environment (here, the argument `modifier`) and returns what that environment maps `a` to.
How do we do the analagous transformation when our `int`s are scattered over the leaves of a tree? How do we turn an `int tree` into a reader?
A tree is not the kind of thing that we can apply a
@@ 293,7 +293,7 @@ it through:
Later, we will talk more about controlling the order in which nodes are visited.
One more revealing example before getting down to business: replacing
`state` everywhere in `tree_monadize` with `list` gives us
+`state` everywhere in `tree_monadize` with `list` lets us do:
# let decider i = if i = 2 then [20; 21] else [i];;
# tree_monadize decider t1;;
@@ 311,11 +311,11 @@ one for each choice of `int`s for its leaves.
Now for the main point. What if we wanted to convert a tree to a list
of leaves?
 type ('a, 'r) continuation = ('a > 'r) > 'r;;
+ type ('r,'a) continuation = ('a > 'r) > 'r;;
let continuation_unit a = fun k > k a;;
let continuation_bind u f = fun k > u (fun a > f a k);;
 let rec tree_monadize (f : 'a > ('b, 'r) continuation) (t : 'a tree) : ('b tree, 'r) continuation =
+ let rec tree_monadize (f : 'a > ('r,'b) continuation) (t : 'a tree) : ('r,'b tree) continuation =
match t with
 Leaf a > continuation_bind (f a) (fun b > continuation_unit (Leaf b))
 Node (l, r) > continuation_bind (tree_monadize f l) (fun l' >
@@ 368,7 +368,7 @@ interesting functions for the first argument of `tree_monadize`:
It's not immediately obvious to us how to simulate the List monadization of the tree using this technique.
We could simulate the tree annotating example by setting the relevant
type to `('a, 'state > 'result) continuation`.
+type to `(store > 'result, 'a) continuation`.
Andre Filinsky has proposed that the continuation monad is
able to simulate any other monad (Google for "mother of all monads").
@@ 391,8 +391,8 @@ natural language meaning.
**Quantification and default quantifier scope construal**.
We saw in the copystring example and in the samefringe example that
local properties of a tree (whether a character is `S` or not, which
+We saw in the copystring example ("abSd") and in the samefringe example that
+local properties of a structure (whether a character is `'S'` or not, which
integer occurs at some leaf position) can control global properties of
the computation (whether the preceeding string is copied or not,
whether the computation halts or proceeds). Local control of
@@ 415,13 +415,13 @@ the following:
 "someone" > Node (Leaf "exists y", k "y")
 _ > k s;;
 let sentence1 = Node (Leaf "John",
+Then we can crudely approximate quantification as follows:
+
+ # let sentence1 = Node (Leaf "John",
Node (Node (Leaf "saw",
Leaf "everyone"),
Leaf "yesterday"));;
Then we can crudely approximate quantification as follows:

# tree_monadize lex sentence1 (fun x > x);;
 : string tree =
Node
@@ 450,17 +450,17 @@ inverse scope:
Node (Leaf "forall x", Node (Leaf "x", Node (Leaf "saw", Leaf "y"))))
There are many crucially important details about quantification that
are being simplified here, and the continuation treatment here is not
+are being simplified here, and the continuation treatment used here is not
scalable for a number of reasons. Nevertheless, it will serve to give
an idea of how continuations can provide insight into the behavior of
quantifiers.
+quantifiers.
The Binary Tree monad

+The Tree monad
+==============
Of course, by now you may have realized that we have discovered a new
monad, the Binary Tree monad. Just as mere lists are in fact a monad,
+Of course, by now you may have realized that we are working with a new
+monad, the binary, leaflabeled Tree monad. Just as mere lists are in fact a monad,
so are trees. Here is the type constructor, unit, and bind:
type 'a tree = Leaf of 'a  Node of ('a tree) * ('a tree);;
@@ 478,20 +478,20 @@ To check the other two laws, we need to make the following
observation: it is easy to prove based on `tree_bind` by a simple
induction on the structure of the first argument that the tree
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`:
+except that each leaf `a` has been replaced with the tree returned by `f a`:
. .
____ ____
    
+   /\ 
a1 . f a1 .
___ ____
    
+    /\
. a5 . f a5
bind ___ f = ____
    
+    /\
. a4 . f a4
____ _____
    
+   /\ /\
a2 a3 f a2 f a3
Given this equivalence, the right identity law
@@ 529,7 +529,7 @@ Now when we bind this tree to `g`, we get
At this point, it should be easy to convince yourself that
using the recipe on the right hand side of the associative law will
built the exact same final tree.
+build the exact same final tree.
So binary trees are a monad.
@@ 542,37 +542,5 @@ that is intended to represent nondeterministic computations as a tree.
What's this have to do with tree\_monadize?

So we've defined a Tree monad:

 type 'a tree = Leaf of 'a  Node of ('a tree) * ('a tree);;
 let tree_unit (a: 'a) : 'a tree = Leaf a;;
 let rec tree_bind (u : 'a tree) (f : 'a > 'b tree) : 'b tree =
 match u with
  Leaf a > f a
  Node (l, r) > Node (tree_bind l f, tree_bind r f);;

What's this have to do with the `tree_monadize` functions we defined earlier?

 let rec tree_monadize (t : 'a tree) (f : 'a > 'b reader) : '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 l f) (fun l' >
 reader_bind (tree_monadize r f) (fun r' >
 reader_unit (Node (l', r'))));;

... and so on for different monads?

Well, notice that `tree\_monadizer` takes arguments whose types
resemble that of a monadic `bind` function. Here's a schematic bind
function compared with `tree\_monadizer`:

 bind (u:'a Monad) (f: 'a > 'b Monad): 'b Monad
 tree\_monadizer (u:'a Tree) (f: 'a > 'b Monad): 'b Tree Monad

Comparing these types makes it clear that `tree\_monadizer` provides a
way to distribute an arbitrary monad M across the leaves of any tree to
form a new tree inside an M box.
+Our different implementations of `tree_monadize` above were different *layerings* of the Tree monad with other monads (Reader, State, List, and Continuation). We'll explore that further here: [[Monad Transformers]].
The more general answer is that each of those `tree\_monadize`
functions is adding a Tree monad *layer* to a preexisting Reader (and
so on) monad. We discuss that further here: [[Monad Transformers]].