Many of you offered a solution along the following lines:

type 'a state = int -> 'a * int;;
let unit (a : 'a) : 'a state =
  fun count -> (a, count);;
let bind (u : 'a state) (f : 'a -> 'b state ) : 'b state =
  fun count -> let (a, count') = u count in f a count';;

(* Looks good so far, now how are we going to increment the count? *)

let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state =
  bind u (fun x ->
    bind v (fun y ->
      fun count -> (f x y, count + 1)));;

Whoops. That will work for the cases you're probably thinking about. For instance, you can do:

lift2 (+) (unit 1) (lift2 (+) (unit 2) (unit 3));;

and you'll get back an int state that when applied to a starting count of 0 yields the result (6, 2)---that is, the result of the computation was 6 and the number of operations was 2.

However, there are several problems here. First off, you shouldn't name your function lift2, because we're using that name for a function that's interdefinable with bind in a specific way. Our canonical lift2 function is:

let lift2 (f : 'a -> 'b -> 'c) (u : 'a state) (v : 'b state) : 'c state =
  bind u (fun x ->
    bind v (fun y ->
      unit (f x y)));;

(Haskell calls this liftM2, and calls our lift either liftM or mapM.)

OK, so then you might call your function loft2 instead. So what?

The remaining problem is more subtle. It's that your solution isn't very modular. You've crafted a tool loft2 that fuses the operation of incrementing the count with the behavior of our lift2. What if we needed to deal with some unary functions as well? Then you'd need a loft1. What if we need to deal with some functions that are already monadic? Then you'd need a tool that fuses the count-incrementing with the behavior of bind. And so on.

It's nicer to just create a little module that does the count-incrementing, and then use that together with the pre-existing apparatus of bind and (our canonical) lift and lift2. You could do that like this:

let tick (a : 'a) : 'a state =
  fun count -> (a, count + 1);;

let result1 =
  bind
    (lift2 (+)
      (unit 1)
      (bind
        (lift2 (+)
          (unit 2)
          (unit 3))
        tick))
    tick;;

result1 0;; (* evaluates to (6, 2) *)

Or like this:

let tock : unit state =
  fun count -> ((), count + 1);;

let result2 =
  bind
    tock
    (fun _ -> lift2 (+)
      (unit 1)
      (bind
        tock
        (fun _ -> lift2 (+)
          (unit 2)
          (unit 3))));;

result2 0;; (* evaluates to (6, 2) *)