A simple question, I hope: The binary package defines two types, Get and Put. The former is essentially a state monad, and the latter is essentially a writer. Both state and writer have reasonable MonadFix instances, so I'd expect that Get and Put also would.
Get does. Put doesn't. So, is it possible to define an appropriate MonadFix instance for Put (really for PutM)?
A more general question is: how does one normally verify that a typeclass instance actually satisfies the laws of that typeclass?
As you can see in the source for the binary package (Data.Binary.Put:71), the data structure used for monadic values is strict in the builder. Since extracting the value from the monad has to force the structure in which the value is found, this will cause an infinite loop if the builder depends on the input.
data PairS a = PairS a !Builder
newtype PutM a = Put { unPut :: PairS a }
So you could write a MonadFix instance, but you wouldn't be able to do anything useful with it. But I don't think you could do anything useful with MonadFix here anyway, at least nothing that you couldn't do with plain old fix, since the PutM monad is basically Writer Builder (but with a specialized implementation).
As for your second question, it's not related to the first so you should ask it as a separate question.