From 73f8e125d9910c93213d357c2779cc743fa22e8b Mon Sep 17 00:00:00 2001 From: Chris Date: Sat, 14 Mar 2015 15:46:15 -0400 Subject: [PATCH] exx --- exercises/_assignment6.mdwn | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+) diff --git a/exercises/_assignment6.mdwn b/exercises/_assignment6.mdwn index 9a3d04c0..2e4f7044 100644 --- a/exercises/_assignment6.mdwn +++ b/exercises/_assignment6.mdwn @@ -112,3 +112,38 @@ our scorecard. On the simple-minded view, we would replace it with `w`. But that's not the right result, because `w` itself has been mapped onto 2. +## Monads + +Mappables (functors), MapNables (applicatives functors), and Monads +(composables) are ways of lifting computations from unboxed types into +boxed types. Here, a "boxed type" is a type function with one missing +piece, which we can think of as a function from a type to a type. +Call this type function M, and let P, Q, R, and S be variables over types. + +Recall that a monad requires a singleton function 1:P-> MP, and a +composition operator >=>: (P->MQ) -> (Q->MR) -> (R->MS) that obey the +following laws: + + 1 >=> k = k + k >=> 1 = k + j >=> (k >=> l) = (j >=> k) >=> l + +For instance, the identity monad has the identity function I for 1 +and ordinary function composition (o) for >=>. It is easy to prove +that the laws hold for any expressions j, k, and l whose types are +suitable for 1 and >=>: + + 1 >=> k == I o k == \p. I (kp) ~~> \p.kp ~~> k + k >=> 1 == k o I == \p. k (Ip) ~~> \p.kp ~~> k + + (j >=> k) >=> l == (\p.j(kp)) o l == \q.(\p.j(kp))(lq) ~~> \q.j(k(lq)) + j >=> (k >=> l) == j o (k o l) == j o \p.k(lp) == \q.j(\p.k(lp)q) ~~> \q.j(k(lq)) + +1. On a number of occasions, we've used the Option type to make our +conceptual world neat and tidy (for instance, think of the discussion +of Kaplan's Plexy). It turns out that there is a natural monad for +the Option type. Borrowing the notation of OCaml, let's say that "`'a +option`" is the type of a boxed `'a`, whatever type `'a` is. Then the +obvious singleton for the Option monad is \p.Just p. What is the +composition operator >=> for the Option monad? Show your answer is +correct by proving that it obeys the monad laws. -- 2.11.0