`â§ (\* mid \*) : P-> `__P__

, and a
+composition operator like `>=> : (P->`__Q__) -> (Q->__R__) -> (P->__R__)

.
+
+As we said in the notes, we'll move freely back and forth between using `>=>` and using `<=<` (aka `mcomp`), which
+is just `>=>` with its arguments flipped. `<=<` has the virtue that it corresponds more
+closely to the ordinary mathematical symbol `â`. But `>=>` has the virtue
+that its types flow more naturally from left to right.
+
+Anyway, `mid`/`â§` and (let's say) `<=<` have to obey the Monad Laws:
+
+ â§ <=< k == k
+ k <=< â§ == k
+ j <=< (k <=< l) == (j <=< k) <=< l
+
+For example, the Identity monad has the identity function `I` for `â§`
+and ordinary function composition `â` for `<=<`. It is easy to prove
+that the laws hold for any terms `j`, `k`, and `l` whose types are
+suitable for `â§` and `<=<`:
+
+ â§ <=< k == I â k == \p. I (k p) ~~> \p. k p ~~> k
+ k <=< â§ == k â I == \p. k (I p) ~~> \p. k p ~~> k
+
+ (j <=< k) <=< l == (\p. j (k p)) â l == \q. (\p. j (k p)) (l q) ~~> \q. j (k (l q))
+ j <=< (k <=< l) == j â (k â l) == j â (\p. k (l p)) == \q. j ((\p. k (l p)) q) ~~> \q. j (k (l q))
+
+1. On a number of occasions, we've used the Option/Maybe type to make our
+conceptual world neat and tidy (for instance, think of [[our discussion
+of Kaplan's Plexy|topics/week6_plexy]]). As we learned in class, there is a natural monad
+for the Option type. Using the vocabulary of OCaml, let's say that
+`'a option` is the type of a boxed `'a`, whatever type `'a` is.
+More specifically,
+
+ type 'a option = None | Some 'a
+
+ (If you have trouble keeping straight what is the OCaml terminology for this and what is the Haskell terminology, don't worry, we do too.)
+
+ Now the obvious singleton for the Option monad is `\p. Some p`. Give
+(or reconstruct) either of the composition operators `>=>` or `<=<`.
+Show that your composition operator obeys the Monad Laws.
+
+ ANSWER
+
+2. Do the same with lists. That is, given an arbitrary type
+`'a`, let the boxed type be `['a]` or `'a list`, that is, lists of values of type `'a`. The `â§`
+is the singleton function `\p. [p]`, and the composition operator is:
+
+ let (>=>) (j : 'a -> 'b list) (k : 'b -> 'c list) : 'a -> 'c list =
+ fun a -> List.flatten (List.map k (j a))
+
+ For example:
+
+ let j a = [a; a+1];;
+ let k b = [b*b; b+b];;
+ (j >=> k) 7
+ (* which OCaml evaluates to:
+ - : int list = [49; 14; 64; 16]
+ *)
+
+ Show that these obey the Monad Laws.
+
+ ANSWER
--
2.11.0