\x. [x]
\x. [odd? x, odd? x]
\x. prime_factors_of x
\x. [0, 0, 0]
map f ○ ⇧ == ⇧ ○ f
map f ○ join == join ○ map (map f)
> The Monad Laws then take the form: >
join ○ (map join) == join ○ join
join ○ ⇧ == id == join ○ map ⇧
> The first of these says that if you have a triply-boxed type, and you first merge the inner two boxes (with `map join`), and then merge the resulting box with the outermost box, that's the same as if you had first merged the outer two boxes, and then merged the resulting box with the innermost box. The second law says that if you take a box type and wrap a second box around it (with `⇧`) and then merge them, that's the same as if you had done nothing, or if you had instead wrapped a second box around each element of the original (with `map ⇧`, leaving the original box on the outside), and then merged them.

> The Category Theorist would state these Laws like this, where `M` is the endofunctor that takes us from type `α` to type α: >

μ ○ M(μ) == μ ○ μ
μ ○ η == id == μ ○ M(η)
> A word of advice: if you're doing any work in this conceptual neighborhood and need a Greek letter, don't use μ. In addition to the preceding usage, there's also a use in recursion theory (for the minimization operator), in type theory (as a fixed point operator for types), and in the λμ-calculus, which is a formal system that deals with _continuations_, which we will focus on later in the course. So μ already exhibits more ambiguity than it can handle. > We link to further reading about the Category Theory origins of Monads below.
There isn't any single `⇧` function, or single `mbind` function, and so on. For each new box type, this has to be worked out in a useful way. And as we hinted, in many cases the choice of box *type* still leaves some latitude about how they should be defined. We commonly talk about "the List Monad" to mean a combination of the choice of `α list` for the box type and particular definitions for the various functions listed above. There's also "the ZipList MapNable/Applicative" which combines that same box type with other choices for (some of) the functions. Many of these packages also define special-purpose operations that only make sense for that system, but not for other Monads or Mappables. As hinted in last week's homework and explained in class, the operations available in a Mappable system exactly preserve the "structure" of the boxed type they're operating on, and moreover are only sensitive to what content is in the corresponding original position. If you say `map f [1,2,3]`, then what ends up in the first position of the result depends only on how `f` and `1` combine. For MapNable operations, on the other hand, the structure of the result may instead be a complex function of the structure of the original arguments. But only of their structure, not of their contents. And if you say `map2 f [10,20] [1,2,3]`, what ends up in the first position of the result depends only on how `f` and `10` and `1` combine. With `map`, you can supply an `f` such that `map f [3,2,0,1] == [[3,3,3],[2,2],[],[1]]`. But you can't transform `[3,2,0,1]` to `[3,3,3,2,2,1]`, and you can't do that with MapNable operations, either. That would involve the structure of the result (here, the length of the list) being sensitive to the content, and not merely the structure, of the original. For Monads (Composables), on the other hand, you can perform more radical transformations of that sort. For example, `join (map (\x. dup x x) [3,2,0,1])` would give us `[3,3,3,2,2,1]` (for a suitable definition of `dup`). ## Interdefinitions and Subsidiary notions## We said above that various of these box type operations can be defined in terms of others. Here is a list of various ways in which they're related. We try to stick to the consistent typing conventions that:
f : α -> β;  g and h have types of the same form
also sometimes these will have types of the form α -> β -> γ
note that α and β are permitted to be, but needn't be, boxed types
j : α -> β; k and l have types of the same form
u : α;      v and xs and ys have types of the same form

w : α
But we may sometimes slip. Here are some ways the different notions are related:
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 == (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 u == u >>= ⇧ ○ f
[3, 2, 0, 1]  >>=α list    (\a -> dup a a)  ==>  [3, 3, 3, 2, 2, 1]

Some a  >>=α option  (\a -> Some 0) ==> Some 0
None    >>=α option  (\a -> Some 0) ==> None
Some a  >>=α option  (\a -> None  ) ==> None

.
/ \
.                                                  /   \
/ \                                  .             .     \
.   3       >>=(α,unit) tree  (\a ->  / \  )  ==>   / \     .
/ \                                  a   a         /   \   / \
1   2                                              .     . 3   3
/ \   / \
1   1 2   2