From 9529dbbf77c27cf56ff2ef50e76024cfd32afff5 Mon Sep 17 00:00:00 2001 From: jim Date: Mon, 23 Mar 2015 10:06:16 -0400 Subject: [PATCH] change mid to double up arrow U+2e17 --- topics/week7_introducing_monads.mdwn | 90 ++++++++++++++++++------------------ 1 file changed, 45 insertions(+), 45 deletions(-) diff --git a/topics/week7_introducing_monads.mdwn b/topics/week7_introducing_monads.mdwn index b1782d8e..9fa55a6c 100644 --- a/topics/week7_introducing_monads.mdwn +++ b/topics/week7_introducing_monads.mdwn @@ -1,4 +1,4 @@ - + The [[tradition in the functional programming @@ -114,13 +114,13 @@ Here are the types of our crucial functions, together with our pronunciation, an > In Haskell, this is called `Control.Applicative.liftA2` and `Control.Monad.liftM2`. -mid (/εmaidεnt@tI/): P -> P +⇧ or mid (/εmaidεnt@tI/): P -> P > This notion is exemplified by `Just` for the box type `Maybe α` and by the singleton function for the box type `List α`. It will be a way of boxing values with your box type that plays a distinguished role in the various Laws and interdefinitions we present below. -> In Haskell, this is called `Control.Monad.return` and `Control.Applicative.pure`. In other theoretical contexts it is sometimes called `unit` or `η`. All of these names are somewhat unfortunate. First, it has little to do with `η`-reduction in the Lambda Calculus. Second, it has little to do with the `() : unit` value we discussed in earlier classes. Third, it has little to do with the `return` keyword in C and other languages; that's more closely related to continuations, which we'll discuss in later weeks. Finally, this doesn't perfectly align with other uses of "pure" in the literature. `mid`'d values _will_ generally be "pure" in the other senses, but other boxed values can be too. +> In Haskell, this is called `Control.Monad.return` and `Control.Applicative.pure`. In other theoretical contexts it is sometimes called `unit` or `η`. All of these names are somewhat unfortunate. First, it has little to do with `η`-reduction in the Lambda Calculus. Second, it has little to do with the `() : unit` value we discussed in earlier classes. Third, it has little to do with the `return` keyword in C and other languages; that's more closely related to continuations, which we'll discuss in later weeks. Finally, this doesn't perfectly align with other uses of "pure" in the literature. `⇧`'d values _will_ generally be "pure" in the other senses, but other boxed values can be too. -> For all these reasons, we're thinking it will be clearer in our discussion to use a different name. In the class presentation Jim called it `𝟭`; but now we've decided that `mid` is better. (Think of it as "m" plus "identity", not as the start of "midway".) +> For all these reasons, we're thinking it will be clearer in our discussion to use a different name. In the class presentation Jim called it `𝟭`; and in an earlier draft of this page we (only) called it `mid` ("m" plus "identity"); but now we're trying out `⇧` as a symbolic alternative. But in the end, we might switch to just using `η`. m$ or mapply (/εm@plai/): P -> Q -> P -> Q @@ -166,74 +166,74 @@ has to obey the following Map Laws: * ***MapNable*** (in Haskelese, "Applicatives") A Mappable box type is *MapNable* - if there are in addition `map2`, `mid`, and `mapply`. (Given either + if there are in addition `map2`, `⇧`, and `mapply`. (Given either of `map2` and `mapply`, you can define the other, and also `map`. Moreover, with `map2` in hand, `map3`, `map4`, ... `mapN` are easily definable.) These have to obey the following MapN Laws: - 1. mid (id : P->P) : P -> P is a left identity for `m$`, that is: `(mid id) m$ xs = xs` - 2. `mid (f a) = (mid f) m$ (mid a)` - 3. The `map2`ing of composition onto boxes `fs` and `gs` of functions, when `m$`'d to a box `xs` of arguments == the `m$`ing of `fs` to the `m$`ing of `gs` to xs: `(mid (○) m$ fs m$ gs) m$ xs = fs m$ (gs m$ xs)`. - 4. When the arguments (the right-hand operand of `m$`) are an `mid`'d value, the order of `m$`ing doesn't matter: `fs m$ (mid x) = mid ($x) m$ fs`. (Though note that it's `mid ($x)`, or `mid (\f. f x)` that gets `m$`d onto `fs`, not the original `mid x`.) Here's an example where the order *does* matter: `[succ,pred] m$ [1,2] == [2,3,0,1]`, but `[($1),($2)] m$ [succ,pred] == [2,0,3,1]`. This Law states a class of cases where the order is guaranteed not to matter. - 5. A consequence of the laws already stated is that when the _left_-hand operand of `m$` is a `mid`'d value, the order of `m$`ing doesn't matter either: `mid f m$ xs == map (flip ($)) xs m$ mid f`. + 1. ⇧ (id : P->P) : P -> P is a left identity for `m$`, that is: `(⇧ id) m$ xs = xs` + 2. `⇧ (f a) = (⇧ f) m$ (⇧ a)` + 3. The `map2`ing of composition onto boxes `fs` and `gs` of functions, when `m$`'d to a box `xs` of arguments == the `m$`ing of `fs` to the `m$`ing of `gs` to xs: `(⇧ (○) m$ fs m$ gs) m$ xs = fs m$ (gs m$ xs)`. + 4. When the arguments (the right-hand operand of `m$`) are an `⇧`'d value, the order of `m$`ing doesn't matter: `fs m$ (⇧ x) = ⇧ ($x) m$ fs`. (Though note that it's `⇧ ($x)`, or `⇧ (\f. f x)` that gets `m$`d onto `fs`, not the original `⇧ x`.) Here's an example where the order *does* matter: `[succ,pred] m$ [1,2] == [2,3,0,1]`, but `[($1),($2)] m$ [succ,pred] == [2,0,3,1]`. This Law states a class of cases where the order is guaranteed not to matter. + 5. A consequence of the laws already stated is that when the _left_-hand operand of `m$` is a `⇧`'d value, the order of `m$`ing doesn't matter either: `⇧ f m$ xs == map (flip ($)) xs m$ ⇧ f`. * ***Monad*** (or "Composables") A MapNable box type is a *Monad* if there - is in addition an associative `mcomp` having `mid` as its left and + is in addition an associative `mcomp` having `⇧` as its left and right identity. That is, the following Monad Laws must hold: mcomp (mcomp j k) l (that is, (j <=< k) <=< l) == mcomp j (mcomp k l) - mcomp mid k (that is, mid <=< k) == k - mcomp k mid (that is, k <=< mid) == k + mcomp mid k (that is, ⇧ <=< k) == k + mcomp k mid (that is, k <=< ⇧) == k You could just as well express the Monad laws using `>=>`: l >=> (k >=> j) == (l >=> k) >=> j - k >=> mid == k - mid >=> k == k + k >=> ⇧ == k + ⇧ >=> k == k 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 P -> P. But they needn't be. Their types only need to "cohere" in the sense that the output type of the one arrow is a boxing of the input type of the next. 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 - mid a >>= k == k a + u >>= ⇧ == u + ⇧ a >>= k == k a - (Also, Haskell calls `mid` `return` or `pure`, but we've stuck to our terminology in this context.) Some authors try to make the first of those Laws look more symmetrical by writing it as: + (Also, Haskell calls `⇧` `return` or `pure`, but we've stuck to our terminology in this context.) Some authors try to make the first of those Laws look more symmetrical by writing it as: (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. + 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 `⇧`, on the one hand, and one of `mcomp`, `mbind`, or `join`, on the other. - > 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`: - > 
map f ○ mid == mid ○ f
map f ○ join == join ○ map (map f)
+ > In Category Theory discussion, the Monad Laws are instead expressed in terms of `join` (which they call `μ`) and `⇧` (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`: + > 
map f ○ ⇧ == ⇧ ○ f
map f ○ join == join ○ map (map f)
> The Monad Laws then take the form: - > 
join ○ (map join) == join ○ join
join ○ mid == id == join ○ map mid
- > 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.

+ > 

join ○ (map join) == join ○ join
join ○ ⇧ == id == join ○ map ⇧
+ > 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 `⇧`) 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 ⇧`, leaving the original box on the outside), and then merged them.

> The Category Theorist would state these Laws like this, where `M` is the endofunctor that takes us from type `α` to type α: > 

μ ○ M(μ) == μ ○ μ
μ ○ η == id == μ ○ M(η)
> 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. > We link to further reading about the Category Theory origins of Monads below. -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. +There isn't any single `⇧` 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. @@ -271,12 +271,12 @@ j >=> k ≡= \a. (j a >>= k) u >>= k == (id >=> k) u; or ((\(). u) >=> k) () u >>= k == join (map k u) join w == w >>= id -map2 f xs ys == xs >>= (\x. ys >>= (\y. mid (f x y))) +map2 f xs ys == xs >>= (\x. ys >>= (\y. ⇧ (f x y))) map2 f xs ys == (map f xs) m$ ys, using m$ as an infix operator fs m$ xs == fs >>= (\f. map f xs) m$ == map2 id -map f xs == mid f m$ xs -map f u == u >>= mid ○ f +map f xs == ⇧ f m$ xs +map f u == u >>= ⇧ ○ f @@ -300,8 +300,8 @@ then a boxed `α` is ... a `bool`. That is, α == α. In terms of the box analogy, the Identity box type is a completely invisible box. With the following definitions: - mid ≡ \p. p, that is, our familiar combinator I - mcomp ≡ \f g x. f (g x), that is, ordinary function composition (○) (aka the B combinator) + mid (* or ⇧ *) ≡ \p. p, that is, our familiar combinator I + mcomp (* or <=< *) ≡ \f g x. f (g x), that is, ordinary function composition (○) (aka the B combinator) Identity is a monad. Here is a demonstration that the laws hold: @@ -414,7 +414,7 @@ For the first failure, we noted that it's easy to define a `map` operation for t 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 P, that is `P -> R`, and returns values of the boxed type Q. -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`. The choice can't depend on the value of `a`, because `mid` needs to work for `a`s of _any_ type. Then the MapNable Laws will entail: +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 `⇧ a = (r0, a)` for some specific `r0` of type `R`. The choice can't depend on the value of `a`, because `⇧` needs to work for `a`s of _any_ type. Then the MapNable Laws will entail: 1. (r0,id) m$ (r,x) == (r,x) 2. (r0,f x) == (r0,f) m$ (r0,x) @@ -433,7 +433,7 @@ For the third failure, that is examples of MapNables that aren't Monads, we'll j ## Further Reading ## -As we mentioned above, the notions of Monads have their origin in Category Theory, where they are mostly specified in terms of (what we call) `mid` and `join`. For advanced study, here are some further links on the relation between monads as we're working with them and monads as they appear in Category Theory: +As we mentioned above, the notions of Monads have their origin in Category Theory, where they are mostly specified in terms of (what we call) `⇧` and `join`. For advanced study, here are some further links on the relation between monads as we're working with them and monads as they appear in Category Theory: [1](http://en.wikipedia.org/wiki/Outline_of_category_theory) [2](http://lambda1.jimpryor.net/advanced_topics/monads_in_category_theory/) [3](http://en.wikibooks.org/wiki/Haskell/Category_theory) -- 2.11.0