<code>>>= or mbind : (<u>Q</u>) -> (Q -> <u>R</u>) -> (<u>R</u>)</code>
-<code>=<< (flip mbind, should we call it mdnib?) (<u>Q</u>) -> (Q -> <u>R</u>) -> (<u>R</u>)</code>
+<code>=<< (flip mbind, should we call it mdnib?) (Q -> <u>R</u>) -> (<u>Q</u>) -> (<u>R</u>)</code>
<code>join: <span class="box2">P</span> -> <u>P</u></code>
if there is a `map` function defined for that box type with the type given above. This
has to obey the following Map Laws:
- TODO LAWS
+ <code>map (id : α -> α) = (id : <u>α</u> -> <u>α</u>)</code>
+ <code>map (g ○ f) = (map g) ○ (map f)</code>
+
+ Essentially these say that `map` is a homomorphism from `(α -> β, ○, id)` to <code>(<u>α</u> -> <u>β</u>, ○', id')</code>, where `○'` and `id'` are `○` and `id` restricted to arguments of type <code><u>_</u></code>. That might be hard to digest because it's so abstract. Think of the following concrete example: if you take a `α list` (that's our <code><u>α</u></code>), and apply `id` to each of its elements, that's the same as applying `id` to the list itself. That's the first law. And if you apply the composition of functions `g ○ f` to each of the list's elements, that's the same as first applying `f` to each of the elements, and then going through the elements of the resulting list and applying `g` to each of those elements. That's the second law. These laws obviously hold for our familiar notion of `map` in relation to lists.
+
* ***MapNable*** (in Haskelese, "Applicatives") A Mappable box type is *MapNable*
if there are in addition `map2`, `mid`, and `mapply`. (Given either
To take a slightly less trivial (and even more useful) example,
consider the box type `α list`, with the following operations:
- mid: α -> [α]
+ mid : α -> [α]
mid a = [a]
- mcomp: (β -> [γ]) -> (α -> [β]) -> (α -> [γ])
- mcomp f g a = concat (map f (g a))
- = foldr (\b -> \gs -> (f b) ++ gs) [] (g a)
- = [c | b <- g a, c <- f b]
+ mcomp : (β -> [γ]) -> (α -> [β]) -> (α -> [γ])
+ mcomp k j a = concat (map k (j a)) = List.flatten (List.map k (j a))
+ = foldr (\b ks -> (k b) ++ ks) [] (j a) = List.fold_right (fun b ks -> List.append (k b) ks) [] (j a)
+ = [c | b <- j a, c <- k b]
-The last three definitions of `mcomp` are all equivalent, and it is easy to see that they obey the monad laws (see exercises TODO).
+In the first two definitions of `mcomp`, we give the definition first in Haskell and then in the equivalent OCaml. The three different definitions of `mcomp` (one for each line) are all equivalent, and it is easy to show that they obey the Monad Laws. (You will do this in the homework.)
-In words, `mcomp 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
+In words, `mcomp k j a` feeds the `a` (which has type `α`) to `j`, which returns a list of `β`s;
+each `β` in that list is fed to `k`, 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
- mcomp f g 7 ==> [49, 50, 14, 15]
+ let j a = [a*a, a+a] in
+ let k b = [b, b+1] in
+ mcomp k j 7 ==> [49, 50, 14, 15]
-`g 7` produced `[49, 14]`, which after being fed through `f` gave us `[49, 50, 14, 15]`.
+`j 7` produced `[49, 14]`, which after being fed through `k` gave us `[49, 50, 14, 15]`.
Contrast that to `m$` (`mapply`, which operates not on two *box-producing functions*, but instead on two *values of a boxed type*, one containing functions to be applied to the values in the other box, via some predefined scheme. Thus:
- let gs = [(\a->a*a),(\a->a+a)] in
+ let js = [(\a->a*a),(\a->a+a)] in
let xs = [7, 5] in
- mapply gs xs ==> [49, 25, 14, 10]
+ mapply js xs ==> [49, 25, 14, 10]
As we illustrated in class, there are clear patterns shared between lists and option types and trees, so perhaps you can see why people want to identify the general structures. But it probably isn't obvious yet why it would be useful to do so. To a large extent, this will only emerge over the next few classes. But we'll begin to demonstrate the usefulness of these patterns by talking through a simple example, that uses the monadic functions of the Option/Maybe box type.