How can I count the number of times bind is applied on a Monad - Example given a state monad, I'd like to count the number of times state changed. How can i best encapsulate this? Should this logic be part of bind operator (with side effect since it increments count) or is there a better way of doing it?
You can't. One of the monad laws is
return x >>= f = f x
which has one bind on the left and none on the right, so no law-abiding monad can observe how many bindings there are.
At best you may have an action
increment :: M ()
in your monad which bumps a counter. (This could be implemented, as you say, using
StateT or similar, or in a couple other essentially isomorphic ways.)