X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek8_reader_monad.mdwn;h=93e2086851d3aa8d435825e1e8d456942a7e9633;hp=4dc0da64fe6cea3a6a223e85f588f872323094f3;hb=HEAD;hpb=c50085365cca4f5c5064ab4d1bc9cde71ff5961e;ds=sidebyside diff --git a/topics/week8_reader_monad.mdwn b/topics/week8_reader_monad.mdwn index 4dc0da64..93e20868 100644 --- a/topics/week8_reader_monad.mdwn +++ b/topics/week8_reader_monad.mdwn @@ -1,34 +1,32 @@ - + -[[!toc levels=2]] -The Reader Monad -================ +[[!toc levels=2]] -The goal for this part is to introduce the Reader Monad, and present -two linguistics applications: binding and intensionality. Along the +The goal for these notes is to introduce the Reader Monad, and present +two linguistic 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 safe-div 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,38 +49,39 @@ _|__ ___|___ / 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 -on the lambda evaluator developed during the previous homework, let's +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 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 `head'` +> 2. Reduce `arg` to `arg'`. +> 3. If `(head' arg')` 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 -called depth-first postorder traversal of the tree.) +finally processing the results of the two subcomputation. (This is +called a depth-first postorder traversal of the tree.) [diagram with arrows traversing the tree] @@ -93,13 +92,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 -well-formed 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). +well-formed subtree. So the process of reduction could be animated by +replacing subtrees with the result of reduction on that subtree, until +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`: