From b13412acbd429e1cc83669d6e881e3d9e98fbda3 Mon Sep 17 00:00:00 2001 From: Chris Date: Mon, 16 Mar 2015 15:35:04 -0400 Subject: [PATCH] edits --- exercises/_assignment6.mdwn | 16 ++++------------ topics/_week7_monads.mdwn | 39 ++++++++++++++++++++++----------------- 2 files changed, 26 insertions(+), 29 deletions(-) diff --git a/exercises/_assignment6.mdwn b/exercises/_assignment6.mdwn index 1ebac0cd..ebc20e06 100644 --- a/exercises/_assignment6.mdwn +++ b/exercises/_assignment6.mdwn @@ -166,23 +166,15 @@ Then the obvious singleton for the Option monad is \p.Just p. Give (or reconstruct) the composition operator >=> we discussed in class. Show your composition operator obeys the monad laws. -2. Do the same with crossy lists. That is, given an arbitrary type -'a, let the boxed type be a list of objects of type 'a. The singleton +2. Do the same with lists. That is, given an arbitrary type +'a, let the boxed type be ['a], i.e., a list of objects of type 'a. The singleton is `\p.[p]`, and the composition operator is - >=> (first:P->[Q]) (second:Q->[R]) :(P->[R]) = fun p -> [r | q <- first p, r <- second q] + >=> (first:P->[Q]) (second:Q->[R]) :(P->[R]) = List.flatten (List.map f (g a)) -Sanity check: +For example: f p = [p, p+1] s q = [q*q, q+q] >=> f s 7 = [49, 14, 64, 16] -3. Do the same for zippy lists. That is, you need to find a -composition operator such that - - f p = [p, p+1] - s q = [q*q, q+q] - >=> f s 7 = [49, 16] - -and then prove it obeys the monad laws. diff --git a/topics/_week7_monads.mdwn b/topics/_week7_monads.mdwn index 32f7ac02..b9be5bae 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)) @@ -157,10 +158,15 @@ consider the box type `Î± List`, with the following operations: mcompose-crossy: (Î² -> [Î³]) -> (Î± -> [Î²]) -> (Î± -> [Î³]) mcompose-crossy f g a = [c | b <- g a, c <- f b] + mcompose-crossy f g a = foldr (\b -> \gs -> (f b) ++ gs) [] (g a) + mcompose-crossy f g a = concat (map f (g a)) +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. +list of Î³s. + +The final result is the concatenation of those lists of Î³s. For example, let f b = [b, b+1] in @@ -169,12 +175,11 @@ For example, 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, +There can be multiple monads for any given box type. For instance, 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 + mcompose-zippy f g a = foldr (\b -> \gs -> f b ++ gs) (g a) [] +so that + mcompose-zippy f g 7 = [49, 14] -- 2.11.0