X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2F_week7_monads.mdwn;h=7d189e4dab6f44745624dfa6ad33228f1b9d43fe;hp=61d50094fe6c41d2064ba29c6f504c62082ff206;hb=cbf542073af9c239529a144e017d9d540fb1de75;hpb=471e06ab9fd5bd6beaf7a9ccd17830b54969a5c7
diff --git a/topics/_week7_monads.mdwn b/topics/_week7_monads.mdwn
index 61d50094..7d189e4d 100644
--- a/topics/_week7_monads.mdwn
+++ b/topics/_week7_monads.mdwn
@@ -1,4 +1,4 @@
-
+
Monads
@@ -8,7 +8,7 @@ The [[tradition in the functional programming
literature|https://wiki.haskell.org/Monad_tutorials_timeline]] is to
introduce monads using a metaphor: monads are spacesuits, monads are
monsters, monads are burritos. We're part of the backlash that
-prefers to say that monads are monads.
+prefers to say that monads are (Just) monads.
The closest we will come to metaphorical talk is to suggest that
monadic types place objects inside of *boxes*, and that monads wrap
@@ -17,22 +17,22 @@ any case, the emphasis will be on starting with the abstract structure
of monads, followed by instances of monads from the philosophical and
linguistics literature.
-### Boxes: type expressions with one free type variable
+## Box types: type expressions with one free type variable
Recall that we've been using lower-case Greek letters
-α, β, γ, ...
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 -> Q
@@ -70,15 +72,16 @@ if `α List` is our box type, we can write the second arrow as
Int -> Int
-We'll need a number of schematic functions to help us maneuver in the presence
-of box types. We will want to define a different instance of each of
-these for whichever box type we're dealing with:
+We'll need a number of classes of functions to help us maneuver in the
+presence of box types. We will want to define a different instance of
+each of these for whichever box type we're dealing with. (This will
+become clearly shortly.)
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 (/m&ash;ptu/): (P -> Q -> R) -> P -> Q -> R
mapply (/εm@plai/): P -> Q -> P -> Q
@@ -92,68 +95,81 @@ 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*** ("composables") A MapNable box type is a *Monad* if there
+ is in addition an `mcompose` and a `join` such that `mid` is
+ 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)
+ mcompose â¡ \fgx.f(gx)
Id is a monad. Here is a demonstration that the laws hold:
- mcompose mid k == (\f\g\x.f(gx)) (\p.p) k
+ mcompose mid k == (\fgx.f(gx)) (\p.p) k
~~> \x.(\p.p)(kx)
~~> \x.kx
~~> k
- mcompose k mid == (\f\g\x.f(gx)) k (\p.p)
+ mcompose k mid == (\fgx.f(gx)) k (\p.p)
~~> \x.k((\p.p)x)
~~> \x.kx
~~> k
- mcompose (mcompose j k) l == mcompose ((\f\g\x.f(gx)) j k) l
+ mcompose (mcompose j k) l == mcompose ((\fgx.f(gx)) j k) l
~~> mcompose (\x.j(kx)) l
- == (\f\g\x.f(gx)) (\x.j(kx)) l
+ == (\fgx.f(gx)) (\x.j(kx)) l
~~> \x.(\x.j(kx))(lx)
~~> \x.j(k(lx))
- mcompose j (mcompose k l) == mcompose j ((\f\g\x.f(gx)) k l)
+ mcompose j (mcompose k l) == mcompose j ((\fgx.f(gx)) k l)
~~> mcompose j (\x.k(lx))
- == (\f\g\x.f(gx)) j (\x.k(lx))
+ == (\fgx.f(gx)) j (\x.k(lx))
~~> \x.j((\x.k(lx)) x)
~~> \x.j(k(lx))
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:
+
+ mid: α -> [α]
+ mid a = [a]
+
+ mcompose: (β -> [γ]) -> (α -> [β]) -> (α -> [γ])
+ mcompose f g a = concat (map f (g a))
+ = foldr (\b -> \gs -> (f b) ++ gs) [] (g a)
+ = [c | b <- g a, c <- f b]
- mcompose f g p = [r | q <- g p, r <- f q]
+These three definitions are all equivalent. 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.
-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,
+For example,
- let f q = [q, q+1] in
- let g p = [p*p, p+p] in
+ let f b = [b, b+1] in
+ let g a = [a*a, a+a] in
mcompose f g 7 = [49, 50, 14, 15]
It is easy to see that these definitions obey the monad laws (see exercises).