Signed-off-by: Jim Pryor <profjim@jimpryor.net>
continuations with embedded `prompt`s (also called `reset`s).
The reason the task is well-suited to the list zipper is in part
continuations with embedded `prompt`s (also called `reset`s).
The reason the task is well-suited to the list zipper is in part
-because the list monad has an intimate connection with continuations.
+because the List monad has an intimate connection with continuations.
deals in monads. We can modify the behavior of the system by swapping
one monad for another. We've already seen how adding a monad can add
a layer of funtionality without disturbing the underlying system, for
deals in monads. We can modify the behavior of the system by swapping
one monad for another. We've already seen how adding a monad can add
a layer of funtionality without disturbing the underlying system, for
-instance, in the way that the reader monad allowed us to add a layer
+instance, in the way that the Reader monad allowed us to add a layer
of intensionality to an extensional grammar, but we have not yet seen
the utility of replacing one monad with other.
of intensionality to an extensional grammar, but we have not yet seen
the utility of replacing one monad with other.
Note that what `tree_map` does is take some unchanging contextual
information---what to do to each leaf---and supplies that information
to each subpart of the computation. In other words, `tree_map` has the
Note that what `tree_map` does is take some unchanging contextual
information---what to do to each leaf---and supplies that information
to each subpart of the computation. In other words, `tree_map` has the
-behavior of a reader monad. Let's make that explicit.
+behavior of a Reader monad. Let's make that explicit.
In general, we're on a journey of making our `tree_map` function more and
more flexible. So the next step---combining the tree transformer with
In general, we're on a journey of making our `tree_map` function more and
more flexible. So the next step---combining the tree transformer with
-a reader monad---is to have the `tree_map` function return a (monadized)
+a Reader monad---is to have the `tree_map` function return a (monadized)
tree that is ready to accept any `int -> int` function and produce the
updated tree.
tree that is ready to accept any `int -> int` function and produce the
updated tree.
Now that we have a tree transformer that accepts a *reader* monad as a
parameter, we can see what it would take to swap in a different monad.
Now that we have a tree transformer that accepts a *reader* monad as a
parameter, we can see what it would take to swap in a different monad.
-For instance, we can use a state monad to count the number of leaves in
+For instance, we can use a State monad to count the number of leaves in
the tree.
type 'a state = int -> 'a * int;;
the tree.
type 'a state = int -> 'a * int;;
Unlike the previous cases, instead of turning a tree into a function
from some input to a result, this transformer replaces each `int` with
Unlike the previous cases, instead of turning a tree into a function
from some input to a result, this transformer replaces each `int` with
-a list of `int`'s. We might also have done this with a Reader Monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List Monad an operation like `fun -> [ i; [2*i; 3*i] ]`. Use small trees for your experiment.
+a list of `int`'s. We might also have done this with a Reader monad, though then our environments would need to be of type `int -> int list`. Experiment with what happens if you supply the `tree_monadize` based on the List monad an operation like `fun -> [ i; [2*i; 3*i] ]`. Use small trees for your experiment.
continuation_bind (tree_monadize f r) (fun r' ->
continuation_unit (Node (l', r'))));;
continuation_bind (tree_monadize f r) (fun r' ->
continuation_unit (Node (l', r'))));;
-We use the continuation monad described above, and insert the
-`continuation` type in the appropriate place in the `tree_monadize` code. Then if we give the `tree_monadize` function an operation that converts `int`s into `'b`-wrapping continuation monads, it will give us back a way to turn `int tree`s into corresponding `'b tree`-wrapping continuation monads.
+We use the Continuation monad described above, and insert the
+`continuation` type in the appropriate place in the `tree_monadize` code. Then if we give the `tree_monadize` function an operation that converts `int`s into `'b`-wrapping Continuation monads, it will give us back a way to turn `int tree`s into corresponding `'b tree`-wrapping Continuation monads.
So for example, we compute:
So for example, we compute:
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 plain `int`, and the continuation `fun _ -> []`. Then given what we've said about `tree_monadize`, what should we expect `tree_monadize (fun a -> fun k -> a :: k a` to do?
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 plain `int`, and the continuation `fun _ -> []`. Then given what we've said about `tree_monadize`, what should we expect `tree_monadize (fun a -> fun k -> a :: k a` to do?
-The continuation monad is amazingly flexible; we can use it to
+The Continuation monad is amazingly flexible; we can use it to
simulate some of the computations performed above. To see how, first
note that an interestingly uninteresting thing happens if we use
`continuation_unit` as our first argument to `tree_monadize`, and then
simulate some of the computations performed above. To see how, first
note that an interestingly uninteresting thing happens if we use
`continuation_unit` as our first argument to `tree_monadize`, and then
- : int = 5
We could simulate the tree state example too, but it would require
- : int = 5
We could simulate the tree state example too, but it would require
-generalizing the type of the continuation monad to
+generalizing the type of the Continuation monad to
type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml).
type ('a, 'b, 'c) continuation = ('a -> 'b) -> 'c;;
If you want to see how to parameterize the definition of the `tree_monadize` function, so that you don't have to keep rewriting it for each new monad, see [this code](/code/tree_monadize.ml).
---------------------
Of course, by now you may have realized that we have discovered a new
---------------------
Of course, by now you may have realized that we have discovered a new
-monad, the binary tree monad:
+monad, the Binary Tree monad:
type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);;
let tree_unit (a: 'a) = Leaf a;;
type 'a tree = Leaf of 'a | Node of ('a tree) * ('a tree);;
let tree_unit (a: 'a) = Leaf a;;