assignment6.mdwn

   1 1.  **Build a State monad.** Based on the division by zero monad,
   2 build a system that will evaluate arithmetic expressions.  Instead of
   3 returning a simple integer as a result, it will deliver the correct
   4 answer along with a count of the number of operations performed during
   5 the calculation.  That is, the desired behavior should be like this:
   6
   7                   # lift2 ( + ) (lift2 ( / ) (unit 20) (unit 2))
   8                                    (lift2 ( * ) (unit 2) (unit 3)) 0;;
   9                       - : int * int = (16, 3)
  10
  11     Here, `lift2` is the function that uses `bind` to prepare an ordinary
  12 arithmetic operator (such as addition `( + )`, division `( / )`, or
  13 multiplication `( * )`) to recieve objects from the counting monad as
  14 arguments.  The response of the interpreter says two things: that
  15 (20/2) + (2\*3) = 16, and that the computation took three arithmetic
  16 steps.  By the way, that zero at the end provides the monadic object
  17 with a starting point (0 relevant computations have occurred previous
  18 to the current computation).
  19
  20    Assume for the purposes of this excercise that no one ever tries to
  21 divide by zero (so there should be no int option types anywhere in
  22 your solution).
  23
  24      You'll need to define a computation monad type, unit, bind, and lift2.
  25 We encourage you to consider this hint: [[hints/Assignment 6 Hint 1]].
  26
  27         See our [commentary](/hints/assignment_6_commentary) on your solutions.
  28
  29
  30 2. Prove that your monad satisfies the monad laws.  First, give
  31 examples illustrating specific cases in which the monad laws are
  32 obeyed, then explain (briefly, not exhaustively) why the laws hold in
  33 general for your unit and bind operators.
  34
  35 3. How would you extend your strategy if you wanted to count
  36 arithmetic operations, but you also wanted to be safe from division by
  37 zero?  This is a deep question: how should you combine two monads into
  38 a single system?  If you don't arrive at working code, you can still
  39 discuss the issues and design choices.