X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek8_reader_monad.mdwn;h=07bba89ef8f44d5eb73703c07c7b0552aa937270;hp=4dc0da64fe6cea3a6a223e85f588f872323094f3;hb=21b63e9b52306376868e526357eee1276408938f;hpb=6ee1ef7d80181ae77bc3a4be1d6a77bdbe0d1e3e 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 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,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 depth-first 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 -well-formed subtree. So the process of reduction could be animated by +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). +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));;