X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;f=topics%2F_week7_monads.mdwn;h=7d189e4dab6f44745624dfa6ad33228f1b9d43fe;hb=7acee0fbdbcefcac2ebf8e27e8b0312767dc575e;hp=32f7ac02fbacef95a6c54fa11de16bc87d194cf9;hpb=30def3dcf083271e4e097c7a90b9937e1a8518c2;p=lambda.git
diff --git a/topics/_week7_monads.mdwn b/topics/_week7_monads.mdwn
index 32f7ac02..7d189e4d 100644
--- a/topics/_week7_monads.mdwn
+++ b/topics/_week7_monads.mdwn
@@ -74,13 +74,14 @@ if `α List` is our box type, we can write the second arrow as
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:
+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 (/maeptu/): (P -> Q -> R) -> P -> Q -> R
+map2 (/m&ash;ptu/): (P -> Q -> R) -> P -> Q -> R
mapply (/εm@plai/): P -> Q -> P -> Q
@@ -108,8 +109,8 @@ if there is a `map` function defined for that box type with the type given above
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 an `mcompose` and a `join` such that `mid` is be
+* ***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:
@@ -124,26 +125,26 @@ 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))
@@ -155,26 +156,21 @@ consider the box type `α List`, with the following operations:
mid: α -> [α]
mid a = [a]
- mcompose-crossy: (β -> [γ]) -> (α -> [β]) -> (α -> [γ])
- mcompose-crossy f g a = [c | b <- g a, c <- f b]
+ 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]
+
+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, `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 b = [b, b+1] in
let g a = [a*a, a+a] in
- mcompose-crossy f g 7 = [49, 50, 14, 15]
+ mcompose 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
-
-