1. Build a State monad. Based on the division by zero monad, build a system that will evaluate arithmetic expressions. Instead of returning a simple integer as a result, it will deliver the correct answer along with a count of the number of operations performed during the calculation. That is, the desired behavior should be like this:

      # lift2 ( + ) (lift2 ( / ) (unit 20) (unit 2))
(lift2 ( * ) (unit 2) (unit 3)) 0;;
- : int * int = (16, 3)


Here, lift2 is the function that uses bind to prepare an ordinary arithmetic operator (such as addition ( + ), division ( / ), or multiplication ( * )) to recieve objects from the counting monad as arguments. The response of the interpreter says two things: that (20/2) + (2*3) = 16, and that the computation took three arithmetic steps. By the way, that zero at the end provides the monadic object with a starting point (0 relevant computations have occurred previous to the current computation).

Assume for the purposes of this excercise that no one ever tries to divide by zero (so there should be no int option types anywhere in your solution).

You'll need to define a computation monad type, unit, bind, and lift2. We encourage you to consider this hint: Assignment 6 Hint 1.

See our commentary on your solutions.

2. Prove that your monad satisfies the monad laws. First, give examples illustrating specific cases in which the monad laws are obeyed, then explain (briefly, not exhaustively) why the laws hold in general for your unit and bind operators.

3. How would you extend your strategy if you wanted to count arithmetic operations, but you also wanted to be safe from division by zero? This is a deep question: how should you combine two monads into a single system? If you don't arrive at working code, you can still discuss the issues and design choices.