more refinements

[lambda.git] / topics / week7_introducing_monads.mdwn

diff --git a/topics/week7_introducing_monads.mdwn b/topics/week7_introducing_monads.mdwn
index fc508a8..b5f1d48 100644 (file)
--- a/topics/week7_introducing_monads.mdwn
+++ b/topics/week7_introducing_monads.mdwn
@@ -212,9 +212,9 @@ has to obey the following Map Laws:
         k >=> mid == k
         mid >=> k == k
 
         k >=> mid == k
         mid >=> k == k
 

-    If you have any of `mcomp`, `mpmoc`, `mbind`, or `join`, you can use them to define the others. Also, with these functions you can define `m$` and `map2` from *MapNables*. So with Monads, all you really need to get the whole system of functions are a definition of `mid`, on the one hand, and one of `mcomp`, `mbind`, or `join`, on the other.
+    If you studied algebra, you'll remember that a mon*oid* is a universe with some associative operation that has an identity. For example, the natural numbers form a monoid with multiplication as the operation and `1` as the identity, or with addition as the operation and `0` as the identity. Strings form a monoid with concatenation as the operation and the empty string as the identity. (This example shows that the operation need not be commutative.) Monads are a kind of generalization of this notion, and that's why they're named as they are. The key difference is that for monads, the values being operated on need not be of the same type. They *can* be, if they're all Kleisli arrows of a single type <code>P -> <u>P</u></code>. But they needn't be. Their types only need to "cohere" in certain ways.

 
 

-    In practice, you will often work with `>>=`. In the Haskell manuals, they express the Monad Laws using `>>=` instead of the composition operators. This looks similar, but doesn't have the same symmetry:
+    In the Haskell manuals, they express the Monad Laws using `>>=` instead of the composition operators `>=>` or `<=<`. This looks similar, but doesn't have the same symmetry:

 
         u >>= (\a -> k a >>= j) == (u >>= k) >>= j
         u >>= mid == u
 
         u >>= (\a -> k a >>= j) == (u >>= k) >>= j
         u >>= mid == u


@@ -224,15 +224,19 @@ has to obey the following Map Laws:
 
         (A >>= \a -> B) >>= \b -> C == A >>= (\a -> B >>= \b -> C)
 
 
         (A >>= \a -> B) >>= \b -> C == A >>= (\a -> B >>= \b -> C)
 

+    If you have any of `mcomp`, `mpmoc`, `mbind`, or `join`, you can use them to define the others. Also, with these functions you can define `m$` and `map2` from *MapNables*. So with Monads, all you really need to get the whole system of functions are a definition of `mid`, on the one hand, and one of `mcomp`, `mbind`, or `join`, on the other.
+
+

     > <small>In Category Theory discussion, the Monad Laws are instead expressed in terms of `join` (which they call `μ`) and `mid` (which they call `η`). These are assumed to be "natural transformations" for their box type, which means that they satisfy these equations with that box type's `map`:
     > <pre>map f ○ mid == mid ○ f<br>map f ○ join == join ○ map (map f)</pre>
     > The Monad Laws then take the form:
     > <pre>join ○ (map join) == join ○ join<br>join ○ mid == id == join ○ map mid</pre>
     > The first of these says that if you have a triply-boxed type, and you first merge the inner two boxes (with `map join`), and then merge the resulting box with the outermost box, that's the same as if you had first merged the outer two boxes, and then merged the resulting box with the innermost box. The second law says that if you take a box type and wrap a second box around it (with `mid`) and then merge them, that's the same as if you had done nothing, or if you had instead wrapped a second box around each element of the original (with `map mid`, leaving the original box on the outside), and then merged them.<p>
     > The Category Theorist would state these Laws like this, where `M` is the endofunctor that takes us from type `α` to type <code><u>α</u></code>:
     > <small>In Category Theory discussion, the Monad Laws are instead expressed in terms of `join` (which they call `μ`) and `mid` (which they call `η`). These are assumed to be "natural transformations" for their box type, which means that they satisfy these equations with that box type's `map`:
     > <pre>map f ○ mid == mid ○ f<br>map f ○ join == join ○ map (map f)</pre>
     > The Monad Laws then take the form:
     > <pre>join ○ (map join) == join ○ join<br>join ○ mid == id == join ○ map mid</pre>
     > The first of these says that if you have a triply-boxed type, and you first merge the inner two boxes (with `map join`), and then merge the resulting box with the outermost box, that's the same as if you had first merged the outer two boxes, and then merged the resulting box with the innermost box. The second law says that if you take a box type and wrap a second box around it (with `mid`) and then merge them, that's the same as if you had done nothing, or if you had instead wrapped a second box around each element of the original (with `map mid`, leaving the original box on the outside), and then merged them.<p>
     > The Category Theorist would state these Laws like this, where `M` is the endofunctor that takes us from type `α` to type <code><u>α</u></code>:

-    > <pre>μ ○ M(μ) == μ ○ μ<br>μ ○ η == id == μ ○ M(η)</pre></small>
-    > A word of advice: if you're doing any work in this conceptual neighborhood and need a Greek letter, don't use μ. In addition to the preceding usage, there's also a use in recursion theory (for the minimization operator), in type theory (as a fixed point operator for types), and in the λμ-calculus, which is a formal system that deals with _continuations_, which we will focus on later in the course. So μ already exhibits more ambiguity than it can handle.
+    > <pre>μ ○ M(μ) == μ ○ μ<br>μ ○ η == id == μ ○ M(η)</pre>
+    > A word of advice: if you're doing any work in this conceptual neighborhood and need a Greek letter, don't use μ. In addition to the preceding usage, there's also a use in recursion theory (for the minimization operator), in type theory (as a fixed point operator for types), and in the λμ-calculus, which is a formal system that deals with _continuations_, which we will focus on later in the course. So μ already exhibits more ambiguity than it can handle.</small>

 
 

+There isn't any single `mid` function, or single `mbind` function, and so on. For each new box type, this has to be worked out in a useful way. And as we hinted, in many cases the choice of box *type* still leaves some latitude about how they should be defined. We commonly talk about "the List Monad" to mean a combination of the choice of `α list` for the box type and particular definitions for the various functions listed above. There's also "the ZipList MapNable/Applicative" which combines that same box type with other choices for (some of) the functions. Many of these packages also define special-purpose operations that only make sense for that system, but not for other Monads or Mappables.

 
 As hinted in last week's homework and explained in class, the operations available in a Mappable system exactly preserve the "structure" of the boxed type they're operating on, and moreover are only sensitive to what content is in the corresponding original position. If you say `map f [1,2,3]`, then what ends up in the first position of the result depends only on how `f` and `1` combine.
 
 
 As hinted in last week's homework and explained in class, the operations available in a Mappable system exactly preserve the "structure" of the boxed type they're operating on, and moreover are only sensitive to what content is in the corresponding original position. If you say `map f [1,2,3]`, then what ends up in the first position of the result depends only on how `f` and `1` combine.
 


@@ -243,7 +247,7 @@ With `map`, you can supply an `f` such that `map f [3,2,0,1] == [[3,3,3],[2,2],[
 For Monads (Composables), on the other hand, you can perform more radical transformations of that sort. For example, `join (map (\x. dup x x) [3,2,0,1])` would give us `[3,3,3,2,2,1]` (for a suitable definition of `dup`).
 
 <!--
 For Monads (Composables), on the other hand, you can perform more radical transformations of that sort. For example, `join (map (\x. dup x x) [3,2,0,1])` would give us `[3,3,3,2,2,1]` (for a suitable definition of `dup`).
 
 <!--

-Some global transformations that we work with in semantics, like Veltman's test functions, can't directly be expressed in terms of the  primitive Monad operations? For example, there's no `j` such that `xs >>= j == mzero` if `xs` anywhere contains the value `1`.
+Some global transformations that we work with in semantics, like Veltman's test functions, can't directly be expressed in terms of the general Monad operations. For example, there's no `j` such that `xs >>= j == mzero` if `xs` anywhere contains the value `1`. That would instead be defined as a special-purpose operation, specific to some restricted class of Monads.

 -->
 
 
 -->