X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=inline;f=topics%2Fweek7_introducing_monads.mdwn;h=c778bb7ea4289febc2cb486cbdc187962969d85b;hb=1ade8f95e78edb0b7dcfd98ad46152d9ad5961b3;hp=b7e962ad0e9966df4afc923272840d3c580ed900;hpb=2f8b13c993878f0dd384afba8c219892ef0fd7e2;p=lambda.git
diff --git a/topics/week7_introducing_monads.mdwn b/topics/week7_introducing_monads.mdwn
index b7e962ad..c778bb7e 100644
--- a/topics/week7_introducing_monads.mdwn
+++ b/topics/week7_introducing_monads.mdwn
@@ -171,27 +171,27 @@ has to obey the following Map Laws:
Moreover, with `map2` in hand, `map3`, `map4`, ... `mapN` are easily definable.) These
have to obey the following MapN Laws:
- 1. ⧠(id : P->P) : P -> P
is a left identity for `¢`, that is: `(⧠id) ¢ xs = xs`
- 2. `⧠(f a) = (⧠f) ¢ (⧠a)`
- 3. The `map2`ing of composition onto boxes `fs` and `gs` of functions, when `¢`'d to a box `xs` of arguments == the `¢`ing of `fs` to the `¢`ing of `gs` to xs: `(⧠(â) ¢ fs ¢ gs) ¢ xs = fs ¢ (gs ¢ xs)`.
- 4. When the arguments (the right-hand operand of `¢`) are an `â§`'d value, the order of `¢`ing doesn't matter: `fs ¢ (⧠x) = ⧠($x) ¢ fs`. (Though note that it's `⧠($x)`, or `⧠(\f. f x)` that gets `¢`d onto `fs`, not the original `⧠x`.) Here's an example where the order *does* matter: `[succ,pred] ¢ [1,2] == [2,3,0,1]`, but `[($1),($2)] ¢ [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 `¢` is a `â§`'d value, the order of `¢`ing doesn't matter either: `⧠f ¢ xs == map (flip ($)) xs ¢ ⧠f`.
+ 1. â§(id : P->P) : P -> P
is a left identity for `¢`, that is: `(â§id) ¢ xs = xs`
+ 2. `â§(f a) = (â§f) ¢ (â§a)`
+ 3. The `map2`ing of composition onto boxes `fs` and `gs` of functions, when `¢`'d to a box `xs` of arguments == the `¢`ing of `fs` to the `¢`ing of `gs` to xs: `(â§(â) ¢ fs ¢ gs) ¢ xs = fs ¢ (gs ¢ xs)`.
+ 4. When the arguments (the right-hand operand of `¢`) are an `â§`'d value, the order of `¢`ing doesn't matter: `fs ¢ (â§x) = â§($x) ¢ fs`. (Though note that it's `â§($x)`, or `â§(\f. f x)` that gets `¢`d onto `fs`, not the original `â§x`.) Here's an example where the order *does* matter: `[succ,pred] ¢ [1,2] == [2,3,0,1]`, but `[($1),($2)] ¢ [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 `¢` is a `â§`'d value, the order of `¢`ing doesn't matter either: `â§f ¢ xs == map (flip ($)) xs ¢ â§f`.
* ***Monad*** (or "Composables") A MapNable box type is a *Monad* if there
@@ -214,7 +214,7 @@ has to obey the following Map Laws:
u >>= (\a -> k a >>= j) == (u >>= k) >>= j
u >>= ⧠== u
- ⧠a >>= k == k a
+ â§a >>= k == k a
(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:
@@ -271,11 +271,11 @@ 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. ⧠(f x y)))
+map2 f xs ys == xs >>= (\x. ys >>= (\y. â§(f x y)))
map2 f xs ys == (map f xs) ¢ ys, using ¢ as an infix operator
fs ¢ xs == fs >>= (\f. map f xs)
¢ == map2 id
-map f xs == ⧠f ¢ xs
+map f xs == â§f ¢ xs
map f u == u >>= ⧠â f
@@ -382,7 +382,7 @@ That can be helpful, but it only enables us to have _zero or one_ elements in th
| [] -> []
| x' :: xs' -> List.append (k x') (catmap f xs')
-Now we can have as many elements in the result for a given `α` as `k` cares to return. Another way to write `catmap k xs` is as (Haskell) `concat (map k cs)` or (OCaml) `List.flatten (List.map k xs)`. And this is just the definition of `mbind` or `>>=` for the List Monad. The definition of `mcomp` or `<=<`, that we gave above, differs only in that it's the way to compose two functions `j` and `k`, that you'd want to `catmap`, rather than the way to `catmap` one of those functions over a value that's already a list.
+Now we can have as many elements in the result for a given `α` as `k` cares to return. Another way to write `catmap k xs` is as (Haskell) `concat (map k xs)` or (OCaml) `List.flatten (List.map k xs)`. And this is just the definition of `mbind` or `>>=` for the List Monad. The definition of `mcomp` or `<=<`, that we gave above, differs only in that it's the way to compose two functions `j` and `k`, that you'd want to `catmap`, rather than the way to `catmap` one of those functions over a value that's already a list.
This example is a good intuitive basis for thinking about the notions of `mbind` and `mcomp` more generally. Thus `mbind` for the option/Maybe type takes an option value, applies `k` to its element (if there is one), and returns the resulting option value. `mbind` for a tree with `α`-labeled leaves would apply `k` to each of the leaves, and return a tree containing arbitrarily large subtrees in place of all its former leaves, depending on what `k` returned.
@@ -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 `⧠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:
+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) ¢ (r,x) == (r,x)
2. (r0,f x) == (r0,f) ¢ (r0,x)
@@ -466,4 +466,4 @@ Here is some other reading:
* [Haskell wikibook on Advanced Monads](http://en.wikibooks.org/wiki/Haskell/Advanced_monads)
* [Haskell wiki on Monad Laws](http://www.haskell.org/haskellwiki/Monad_laws)
-There's a long list of monad tutorials linked at the [[Haskell wiki|https://wiki.haskell.org/Monad_tutorials_timeline]] (we linked to this at the top of the page), and on our own [[Offsite Reading]] page. (Skimming the titles is somewhat amusing.) If you are confused by monads, make use of these resources. Read around until you find a tutorial pitched at a level that's helpful for you.
+There's a long list of monad tutorials linked at the [[Haskell wiki|https://wiki.haskell.org/Monad_tutorials_timeline]] (we linked to this at the top of the page), and on our own [[Offsite Reading|/readings]] page. (Skimming the titles is somewhat amusing.) If you are confused by monads, make use of these resources. Read around until you find a tutorial pitched at a level that's helpful for you.