spoke too soon, added examples of failures
authorjim <jim@web>
Fri, 20 Mar 2015 19:42:22 +0000 (15:42 -0400)
committerLinux User <ikiwiki@localhost.members.linode.com>
Fri, 20 Mar 2015 19:42:22 +0000 (15:42 -0400)
topics/week7_introducing_monads.mdwn

index bc719e0..4488a59 100644 (file)
@@ -352,11 +352,33 @@ Contrast that to `m$` (`mapply`), which operates not on two *box-producing funct
     mapply js xs ==> [49, 25, 14, 10]
 
 
     mapply js xs ==> [49, 25, 14, 10]
 
 
-As we illustrated in class, there are clear patterns shared between lists and option types and trees, so perhaps you can see why people want to figure out the general structures. But it probably isn't obvious yet why it would be useful to do so. To a large extent, this will only emerge over the next few classes. But we'll begin to demonstrate the usefulness of these patterns by talking through a simple example, that uses the monadic functions of the Option/Maybe box type.
+The question came up in class of when box types might fail to be Mappable, or Mappables might fail to be MapNables, or MapNables might fail to be Monads.
+
+For the first failure, we noted that it's easy to define a `map` operation for the box type `R -> α`, for a fixed type `R`. You `map` a function of type `P -> Q` over a value of the boxed type <code><u>P</u></code>, that is `R -> P`, by just returning a function that takes some `R` as input, first supplies it to your `R -> P` value, and then supplies the result to your `map`ped function of type `P -> Q`. (We will be working with this Mappable extensively; in fact it's not just a Mappable but more specifically a Monad.)
+
+But if on the other hand, your box type is `α -> R`, you'll find that there is no way to define a `map` operation that takes arbitrary functions of type `P -> Q` and values of the boxed type <code><u>P</u></code>, that is `P -> R`, and returns values of the boxed type <code><u>Q</u></code>.
+
+For the second failure, that is cases of Mappables that are not MapNables, we cited box types like `(R, α)`, for arbitrary fixed types `R`. The `map` operation for these is defined by `map f (r,a) = (r, f a)`. For certain choices of `R` these can be MapNables too. The easiest case is when `R` is the type of `()`. But when we look at the MapNable Laws, we'll see that they impose constraints we cannot satisfy for *every* choice of the fixed type `R`. Here's why. We'll need to define `mid a = (r0, a)` for some specific `r0` of type `R`. Then the MapNable Laws will entail:
+
+    1. (r0,id) m$ (r,x) == (r,x)
+    2. (r0,f x) == (r0,f) m$ (r0,x)
+    3. (r0,(○)) m$ (r'',f) m$ (r',g) m$ (r,x) == (r'',f) m$ ((r',g) m$ (r,x))
+    4. (r'',f) m$ (r0,x) == (r0,($x)) m$ (r'',f)
+    5. (r0,f) m$ (r,x) == (r,($x)) m$ (r0,f)
+
+Now we are not going to be able to write a `m$` function that inspects the second element of its left-hand operand to check if it's the `id` function; the identity of functions is not decidable. So the only way to satisfy Law 1 will be to use the first element of the right-hand operand (`r`) at least in those cases when the first element of the left-hand operand is `r0`. But then that means that the result of the lhs of Law 5 will also have a first element of `r`; so, turning now to the rhs of Law 5, we see that `m$` must use the first element of its _left_-hand operand (here again `r`) at least in those cases when the first element of its right-hand operand is `r0`. If our `R` type has a natural *monoid* structure, we could just let `r0` be the monoid's identity, and have `m$` combine other `R`s using the monoid's operation. Alternatively, if the `R` type is one that we can safely apply the predicate `(r0==)` to, then we could define `m$` something like this:
+
+    let (m$) (r1,f) (r2,x) = ((if r0==r1 then r2 else if r0==r2 then r1 else ...), ...)
+
+But for some types neither of these will be the case. For function types, as we already mentioned, `==` is not decidable. If the functions have suitable types, they do form a monoid with `○` as the operation and `id` as the identity; but many function types won't be such that arbitrary functions of that type are composable. So when `R` is the type of functions from `int`s to `bool`s, for example, we won't have any way to write a `m$` that satisfies the constraints stated above.
+
+For the third failure, that is examples of MapNables that aren't Monads, we'll just state that lists where the `map2` operation is taken to be zipping rather than taking the Cartesian product (what in Haskell are called `ZipList`s), these are claimed to exemplify that failure. But we aren't now in a position to demonstrate that to you.
 
 
 ## Safe division ##
 
 
 
 ## Safe division ##
 
+As we discussed in class, there are clear patterns shared between lists and option types and trees, so perhaps you can see why people want to figure out the general structures. But it probably isn't obvious yet why it would be useful to do so. To a large extent, this will only emerge over the next few classes. But we'll begin to demonstrate the usefulness of these patterns by talking through a simple example, that uses the monadic functions of the Option/Maybe box type.
+
 Integer division presupposes that its second argument
 (the divisor) is not zero, upon pain of presupposition failure.
 Here's what my OCaml interpreter says:
 Integer division presupposes that its second argument
 (the divisor) is not zero, upon pain of presupposition failure.
 Here's what my OCaml interpreter says: