From 21b63e9b52306376868e526357eee1276408938f Mon Sep 17 00:00:00 2001
From: jim
Date: Mon, 6 Apr 2015 07:48:18 0400
Subject: [PATCH] some cleanup

topics/week8_reader_monad.mdwn  349 +++++++++++++++++++++
1 file changed, 180 insertions(+), 169 deletions()
diff git a/topics/week8_reader_monad.mdwn b/topics/week8_reader_monad.mdwn
index 4dc0da64..07bba89e 100644
 a/topics/week8_reader_monad.mdwn
+++ b/topics/week8_reader_monad.mdwn
@@ 6,29 +6,29 @@ The Reader Monad
================
The goal for this part is to introduce the Reader Monad, and present
two linguistics applications: binding and intensionality. Along the
+two linguistics applications: binding and intensionality. Along the
way, we'll continue to think through issues related to order, and a
related notion of flow of information.
At this point, we've seen monads in general, and three examples of
monads: the identity monad (invisible boxes), the Maybe monad (option
types), and the List monad.
+monads: the Identity monad (invisible boxes), the Option/Maybe monad (option
+types), and the List monad.
We've also seen an application of the Maybe monad to safe division.
The starting point was to allow the division function to return an int
option instead of an int. If we divide 6 by 2, we get the answer Just
3. But if we divide 6 by 0, we get the answer Nothing.
+We've also seen an application of the Option/Maybe monad to safe division.
+The starting point was to allow the division function to return an `int
+option` instead of an `int`. If we divide `6` by `2`, we get the answer `Some
+3`. But if we divide `6` by `0`, we get the answer `None`.
The next step was to adjust the other arithmetic functions to teach
them what to do if they received Nothing instead of a boxed integer.
This meant changing the type of their input from ints to int options.
+them what to do if they received `None` instead of a boxed integer.
+This meant changing the type of their input from `int`s to `int option`s.
But we didn't need to do this piecemeal; rather, we "lift"ed the
ordinary arithmetic operations into the monad using the various tools
provided by the monad.
+provided by the monad.
We'll go over this lifting operation in detail in the next section.
## Tracing the effect of safediv on a larger computation
+## Tracing the effect of `safe_div` on a larger computation
So let's see how this works in terms of a specific computation.
@@ 51,37 +51,37 @@ ___ ______
/ 6
No matter which arithmetic operation we begin with, this computation
should eventually reduce to 13. Given a specific reduction strategy,
we can watch the order in which the computation proceeds. Following
+No matter what order we evaluate it in, this computation
+should eventually reduce to `13`. Given a specific reduction strategy,
+we can watch the order in which the computation proceeds. Following
on the lambda evaluator developed during the previous homework, let's
adopt the following reduction strategy:
 In order to reduce an expression of the form (head arg), do the following in order:
 1. Reduce head to h'
 2. Reduce arg to a'.
 3. If (h' a') is a redex, reduce it.
+> In order to reduce an expression of the form (head arg), do the following in order:
+> 1. Reduce head to h'
+> 2. Reduce arg to a'.
+> 3. If (h' a') is a redex, reduce it.
There are many details left unspecified here, but this will be enough
for today. The order in which the computation unfolds will be

 1. Reduce head (+ 1) to itself
 2. Reduce arg ((* ((/ 6) 2)) 3)
 1. Reduce head (* ((/ 6) 2))
 1. Reduce head *
 2. Reduce arg ((/ 6) 2)
 1. Reduce head (/ 6) to itself
 2. Reduce arg 2 to itself
 3. Reduce ((/ 6) 2) to 3
 3. Reduce (* 3) to itself
 2. Reduce arg 4 to itself
 3. Reduce ((* 3) 4) to 12
 3. Reduce ((+ 1) 12) to 13
+for today. The order in which the computation unfolds will be
+
+> 1. Reduce head (+ 1) to itself
+> 2. Reduce arg ((* ((/ 6) 2)) 4)
+> 1. Reduce head (* ((/ 6) 2))
+> 1. Reduce head * to itself
+> 2. Reduce arg ((/ 6) 2)
+> 1. Reduce head (/ 6) to itself
+> 2. Reduce arg 2 to itself
+> 3. Reduce ((/ 6) 2) to 3
+> 3. Reduce (* 3) to itself
+> 2. Reduce arg 4 to itself
+> 3. Reduce ((* 3) 4) to 12
+> 3. Reduce ((+ 1) 12) to 13
This reduction pattern follows the structure of the original
expression exactly, at each node moving first to the left branch,
processing the left branch, then moving to the right branch, and
finally processing the results of the two subcomputation. (This is
+finally processing the results of the two subcomputation. (This is
called depthfirst postorder traversal of the tree.)
[diagram with arrows traversing the tree]
@@ 93,13 +93,13 @@ It will be helpful to see how the types change as we make adjustments.
type tree = Leaf of contents  Branch of tree * tree
Never mind that these types will allow us to construct silly
arithmetric trees such as `+ *` or `2 3`. Note that during the
+arithmetric trees such as `+ *` or `2 3`. Note that during the
reduction sequence, the result of reduction was in every case a
wellformed subtree. So the process of reduction could be animated by
+wellformed subtree. So the process of reduction could be animated by
replacing subtrees with the result of reduction on that subtree, till
the entire tree is replaced by a single integer (namely, 13).
+the entire tree is replaced by a single integer (namely, `13`).
Now we replace the number 2 with 0:
+Now we replace the number `2` with `0`:
int > int` to `int > int > int option`; but since we now have to
anticipate the possibility that any argument might involve division by
+> int > int` at least to `int > int > int option`; but since we now have to
+anticipate the possibility that *any* argument might involve division by
zero inside of it, it would be better to prepare for the possibility
that any subcomputation might return here is the net result for our
types. The easy way to do that is to change (only) the type of num
from int to int option, leaving everying else the same:
+that any subcomputation might return `None` here. So our operators should have
+the type `int option > int option > int option`. Let's bring that about
+by just changing the type `num` from `int` to `int option`, leaving everying else the same:
type num = int option
type contents = Num of num  Op2 of (num > num > num)
type tree = Leaf of contents  Branch of tree * tree
The only difference is that instead of defining our numbers to be
simple integers, they are now int options; and so Op is an operator
over int options.
+simple integers, they are now `int option`s; and so `Op` is an operator
+over `int option`s.
At this point, we bring in the monadic machinery. In particular, here
is the â§ and the map2 function from the notes on safe division:
+At this point, we bring in the monadic machinery. In particular, here
+is the `â§` and the `map2` function from the notes on safe division:
 â§ (a: 'a) = Just a;;
+ â§ (a: 'a) = Some a;;
 map2 (g : 'a > 'b > 'c) (u : 'a option) (v : 'b option) =
 match u with
+ map2 (g : 'a > 'b > 'c) (xx : 'a option) (yy : 'b option) =
+ match xx with
 None > None
 Some x >
 (match v with
+ (match yy with
 None > None
 Some y > Some (g x y));;
Then we lift the entire computation into the monad by applying â§ to
the integers, and by applying `map2` to the operators:
+Then we lift the entire computation into the monad by applying `â§` to
+the integers, and by applying `map2` to the operators. Only, we will replace `/` with `safe_div`, defined as follows:
+
+ safe_div (xx : 'a option) (yy : 'b option) =
+ match xx with
+  None > None
+  Some x >
+ (match yy with
+  None > None
+  Some 0 > None
+  Some y > Some ((/) x y));;