author Chris Barker Wed, 8 Dec 2010 22:43:32 +0000 (17:43 -0500) committer Chris Barker Wed, 8 Dec 2010 22:43:32 +0000 (17:43 -0500)

index 3247ce6..23abaa6 100644 (file)
@@ -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 (leaf_modifier : 'a -> 'b) (t : 'a tree) : 'b tree =
+       let rec tree_map (t : 'a tree) (leaf_modifier : 'a -> 'b): 'b tree =
match t with
| Leaf i -> Leaf (leaf_modifier i)
-           | Node (l, r) -> Node (tree_map leaf_modifier l,
-                                  tree_map leaf_modifier r);;
+           | Node (l, r) -> Node (tree_map l leaf_modifier,
+                                  tree_map r leaf_modifier);;

-`tree_map` takes 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:
+`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 double t1;;
+       tree_map t1 double;;
- : 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 square t1;;
+       tree_map t1 square;;
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))

@@ -114,7 +114,7 @@ with `f i`.

[Application note: this kind of reader object could provide a model
for Kaplan's characters.  It turns an ordinary tree into one that
-expects contextual information (here, the `&lambda; f`) that can be
+expects contextual information (here, the `\f`) that can be
used to compute the content of indexicals embedded arbitrarily deeply
in the tree.]

@@ -143,11 +143,11 @@ function of type `int -> int` to.

But we can do this:

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

This function says: give me a function `f` that knows how to turn
@@ -185,17 +185,17 @@ Then we can expect that supplying it to our `int tree reader` will double all th
In more fanciful terms, the `tree_monadize` function builds plumbing that connects all of the leaves of a tree into one connected monadic network; it threads the

- : int tree =
Node (Node (Leaf 4, Leaf 6), Node (Leaf 10, Node (Leaf 14, Leaf 22)))

Here, our environment is the doubling function (`fun i -> i + i`).  If
-int_readerize t1`) to a different `int -> int` function---say, the
+t1 int_readerize`) to a different `int -> int` function---say, the
squaring function, `fun i -> i * i`---we get an entirely different
result:

- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))

@@ -213,16 +213,16 @@ Gratifyingly, we can use the `tree_monadize` function without any
modification whatsoever, except for replacing the (parametric) type
`'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 =
+       let rec tree_monadize (t : 'a tree) (f : 'a -> 'b state) : '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' ->
+           | Node (l, r) -> state_bind (tree_monadize l f) (fun l' ->
+                              state_bind (tree_monadize r f) (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;;
+       # tree_monadize t1 (fun a -> fun s -> (a, s+1)) 0;;
- : int tree * int =
(Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11))), 5)

@@ -250,7 +250,7 @@ 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;;
+        # tree_monadize t1 (fun a -> fun s -> (s+1, s+1)) 0;;
- : int tree * int =
(Node (Node (Leaf 1, Leaf 2), Node (Leaf 3, Node (Leaf 4, Leaf 5))), 5)

@@ -262,14 +262,14 @@ 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 =
+       let rec tree_monadize_rev (t : 'a tree) (f : 'a -> 'b state) : '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' ->     (* R first *)
-                              state_bind (tree_monadize f l) (fun l'->    (* Then L  *)
+           | Node (l, r) -> state_bind (tree_monadize r f) (fun r' ->     (* R first *)
+                              state_bind (tree_monadize l f) (fun l'->    (* Then L  *)
state_unit (Node (l', r'))));;

-        # tree_monadize_rev (fun a -> fun s -> (s+1, s+1)) t1 0;;
+        # tree_monadize_rev t1 (fun a -> fun s -> (s+1, s+1)) 0;;
- : int tree * int =
(Node (Node (Leaf 5, Leaf 4), Node (Leaf 3, Node (Leaf 2, Leaf 1))), 5)

@@ -280,7 +280,7 @@ same-fringe problem.
One more revealing example before getting down to business: replacing
`state` everywhere in `tree_monadize` with `list` gives us

-       # tree_monadize (fun i -> [ [i; square i] ]) t1;;
+       # tree_monadize t1 (fun i -> [ [i; square i] ]);;
- : int list tree list =
[Node
(Node (Leaf [2; 4], Leaf [3; 9]),
@@ -303,11 +303,11 @@ of leaves?
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 (t : 'a tree) (f : 'a -> ('b, 'r) continuation) : ('b tree, 'r) 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' ->
-                              continuation_bind (tree_monadize f r) (fun r' ->
+           | Node (l, r) -> continuation_bind (tree_monadize l f) (fun l' ->
+                              continuation_bind (tree_monadize r f) (fun r' ->
continuation_unit (Node (l', r'))));;

We use the Continuation monad described above, and insert the
@@ -315,12 +315,12 @@ We use the Continuation monad described above, and insert the

So for example, we compute:

-       # tree_monadize (fun a -> fun k -> a :: k a) t1 (fun t -> []);;
+       # tree_monadize t1 (fun a k -> a :: k ()) (fun _ -> []);;
- : int list = [2; 3; 5; 7; 11]

We have found a way of collapsing a tree into a list of its
leaves. Can you trace how this is working? Think first about what the
-operation `fun a -> fun k -> a :: k a` does when you apply it to a
+operation `fun a k -> a :: k a` does when you apply it to a
plain `int`, and the continuation `fun _ -> []`. Then given what we've
a -> fun k -> a :: k a` to do?
@@ -337,7 +337,7 @@ note that an interestingly uninteresting thing happens if we use
`continuation_unit` as our first argument to `tree_monadize`, and then
apply the result to the identity function:

-       # tree_monadize continuation_unit t1 (fun t -> t);;
+       # tree_monadize t1 continuation_unit (fun t -> t);;
- : int tree =
Node (Node (Leaf 2, Leaf 3), Node (Leaf 5, Node (Leaf 7, Leaf 11)))

@@ -345,19 +345,19 @@ That is, nothing happens.  But we can begin to substitute more
interesting functions for the first argument of `tree_monadize`:

(* Simulating the tree reader: distributing a operation over the leaves *)
-       # tree_monadize (fun a -> fun k -> k (square a)) t1 (fun t -> t);;
+       # tree_monadize t1 (fun a -> fun k -> k (square a)) (fun t -> t);;
- : int tree =
Node (Node (Leaf 4, Leaf 9), Node (Leaf 25, Node (Leaf 49, Leaf 121)))

(* Simulating the int list tree list *)
-       # tree_monadize (fun a -> fun k -> k [a; square a]) t1 (fun t -> t);;
+       # tree_monadize t1 (fun a -> fun k -> k [a; square a]) (fun t -> t);;
- : int list tree =
Node
(Node (Leaf [2; 4], Leaf [3; 9]),
Node (Leaf [5; 25], Node (Leaf [7; 49], Leaf [11; 121])))

(* Counting leaves *)
-       # tree_monadize (fun a -> fun k -> 1 + k a) t1 (fun t -> 0);;
+       # tree_monadize t1 (fun a -> fun k -> 1 + k a) (fun t -> 0);;
- : int = 5

[To be fixed: exactly which kind of monad each of these computations simulates.]
@@ -423,7 +423,7 @@ let sentence1 = Node (Leaf "John",
Then we can crudely approximate quantification as follows:

<pre>
-# tree_monadize lex sentence1 (fun x -> x);;
+# tree_monadize sentence1 lex (fun x -> x);;
- : string tree =
Node
(Leaf "forall x",
@@ -436,7 +436,7 @@ sentence:

<pre>
# let sentence2 = Node (Leaf "everyone", Node (Leaf "saw", Leaf "someone"));;
-# tree_monadize lex sentence2 (fun x -> x);;
+# tree_monadize sentence2 lex (fun x -> x);;
- : string tree =
Node
(Leaf "forall x",
@@ -448,7 +448,7 @@ replace the usual tree_monadizer with tree_monadizer_rev, we get
inverse scope:

<pre>
-# tree_monadize_rev lex sentence2 (fun x -> x);;
+# tree_monadize_rev sentence2 lex (fun x -> x);;
- : string tree =
Node
(Leaf "exists y",
@@ -559,14 +559,26 @@ So we've defined a Tree monad:

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

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

... 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