`α, β, γ, ...`

to represent types. We'll
+`α, β, γ, ...`

as variables over types. We'll
use `P`, `Q`, `R`, and `S` as metavariables over type schemas, where a
type schema is a type expression that may or may not contain unbound
type variables. For instance, we might have
- P â¡ Int
- P â¡ Î± -> Î±
- P â¡ âÎ±. Î± -> Î±
- P â¡ âÎ±. Î± -> Î²
+ P_1 â¡ Int
+ P_2 â¡ Î± -> Î±
+ P_3 â¡ âÎ±. Î± -> Î±
+ P_4 â¡ âÎ±. Î± -> Î²
etc.
-A box type will be a type expression that contains exactly one free
+A *box type* will be a type expression that contains exactly one free
type variable. Some examples (using OCaml's type conventions):
Î± Maybe
@@ -53,6 +53,8 @@ would write
for the type of a boxed Int.
+## Kleisli arrows
+
At the most general level, we'll talk about *Kleisli arrows*:
P -> `mid (/εmaidεnt@tI/ aka unit, return, pure): P -> `__P__

`map (/maep/): (P -> Q) -> `__P__ -> __Q__

-`map2 (/maep/): (P -> Q -> R) -> `__P__ -> __Q__ -> __R__

+`map2 (/maeptu/): (P -> Q -> R) -> `__P__ -> __Q__ -> __R__

`mapply (/εm@plai/): `__P -> Q__ -> __P__ -> __Q__

@@ -92,30 +94,34 @@ these for whichever box type we're dealing with:
`mjoin: `__P__ -> __P__

-Note that `mcompose` and `mbind` are interdefinable: `u >=> k â¡ \a. (ja >>= k)`

.
+The managerie isn't quite as bewildering as you might suppose. For
+one thing, `mcompose` and `mbind` are interdefinable: ```
u >=> k â¡
+\a. (ja >>= k)
```

.
-In most cases of interest, the specific instances of these types will
-provide certain useful guarantees.
+In most cases of interest, instances of these types will provide
+certain useful guarantees.
-* ***Mappable*** ("functors") At the most general level, some box types are *Mappable*
-if there is a `map` function defined for that boxt type with the type given above.
+* ***Mappable*** ("functors") At the most general level, box types are *Mappable*
+if there is a `map` function defined for that box type with the type given above.
* ***MapNable*** ("applicatives") A Mappable box type is *MapNable*
- if there are in addition `map2`, `mid`, and `mapply`.
+ if there are in addition `map2`, `mid`, and `mapply`. (With
+ `map2` in hand, `map3`, `map4`, ... `mapN` are easily definable.)
-* ***Monad*** ("composable") A MapNable box type is a *Monad* if
- there is in addition a `mcompose` and `join`. In addition, in
- order to qualify as a monad, `mid` must be a left and right
- identity for mcompose, and mcompose must be associative. That
- is, the following "laws" must hold:
+* ***Monad*** ("composable") A MapNable box type is a *Monad* if there
+ is in addition an `mcompose` and a `join` such that `mid` is be
+ a left and right identity for `mcompose`, and `mcompose` is
+ associative. That is, the following "laws" must hold:
mcompose mid k = k
mcompose k mid = k
mcompose (mcompose j k) l = mcompose j (mcompose k l)
-To take a trivial example (but still useful, as we will see), consider
-the identity box type Id: `Î± -> Î±`. In terms of the box analogy, the
-Identity box type is an invisible box. With the following definitions
+To take a trivial (but, as we will see, still useful) example,
+consider the identity box type Id: `Î± -> Î±`. So if Î± is type Bool,
+then a boxed Î± is ... a Bool. In terms of the box analogy, the
+Identity box type is a completly invisible box. With the following
+definitions
mid â¡ \p.p
mcompose â¡ \f\g\x.f(gx)
@@ -143,18 +149,32 @@ Id is a monad. Here is a demonstration that the laws hold:
Id is the favorite monad of mimes everywhere.
-To take a slightly less trivial example, consider the box type `Î±
-List`, with the following operations:
+To take a slightly less trivial (and even more useful) example,
+consider the box type `Î± List`, with the following operations:
- mcompose f g p = [r | q <- g p, r <- f q]
+ mid: Î± -> [Î±]
+ mid a = [a]
+
+ mcompose-crossy: (Î² -> [Î³]) -> (Î± -> [Î²]) -> (Î± -> [Î³])
+ mcompose-crossy f g a = [c | b <- g a, c <- f b]
-In words, if g maps a P to a list of Qs, and f maps a Q to a list of
-Rs, then mcompose f g maps a P to a list of Rs by first feeding the P
-to g, then feeding each of the Qs delivered by g to f. For example,
+In words, `mcompose f g a` feeds the a (which has type Î±) to g, which
+returns a list of Î²s; each Î² in that list is fed to f, which returns a
+list of Î³s. The final result is the concatenation of those lists of Î³s.
+For example,
- let f q = [q, q+1] in
- let g p = [p*p, p+p] in
- mcompose f g 7 = [49, 50, 14, 15]
+ let f b = [b, b+1] in
+ let g a = [a*a, a+a] in
+ mcompose-crossy f g 7 = [49, 50, 14, 15]
It is easy to see that these definitions obey the monad laws (see exercises).
+There can be multiple monads for any given box type. For isntance,
+using the same box type and the same mid, we can define
+
+ mcompose-zippy f g a = match (f,g) with
+ ([],_) -> []
+ (_,[]) -> []
+ (f:ftail, g:gtail) -> f(ga) && mcompoze-zippy ftail gtail a
+
+