I was thinking about creating a generic monad that can persist state change even when fail is called. The StateT monad will discard the state change so it makes it hard to add tracing to the program. (at least to me. If there's any nice way of doing this, please kindly instruct me.)

If you have (StateT m) where m is MonadIO or a ST monad, you can replace (StateT m) with (ReaderT m). That is, you can allocate IORef and make that IORef the (reader) environment for the further computation. The mutations done to the IORef would not be backtracked on failure. In the case of an IO monad, the conversion from (StateT IO) to a (ReaderT IO) has another important advantage. The exception handling primitives like catch work only with IO itself (not with MonadIO). In the case of (ReaderT IO), it is easy to strip out the environment and get the IO itself. This is not the case with (StateT IO).

to_write :: ((x->a)->r) -> (x->(a,s)) -> (r,s) to_write f1 f2 = ...

I can't get a data of type x, so the only way is to pass f2 into f1. In order to pass f2 to f1, I have to discard the s returned by f2. Thus, I lose the s forever.

That is, we can only do f1 (fst . f2) to get the result 'r', Right? The problem is getting snd . f2. I'm afraid the problem seems to be underspecified. What if 'f1' never calls f2? What kind of value of type 's' should we return from to_write? What if f1 calls, f2 1024 times? Which of the 's' values should we return? I think I understand what you were trying to accomplish. 's' signifies something like 'invocation counter'. We would like to count the number of invocation of a specific function, without disturbing the rest of the code. I'm afraid the most robust solution is to use IORef. If you are not in the IO monad, you have to use unsafePerformIO then, something like the following to_write f1 f2 = let sr = unsafePerformIO (newIORef undefined) in let r = f1 (\x -> let (a,s) = f2 x in seq (unsafePerformIO (writeIORef sr s)) a) in seq r (r, (unsafePerformIO (readIORef sr))) If you compile the code, you also need to write a pragma to prevent inlining. OTH, if the compiler does inline 'sr', you merely get an error. If you're already in a monad, things are simpler, of course. If the types 'r', 'x' and 'a' are in the class Num, another approach might be plausible: data NewNum a = NewNum a Int -- assuming that 's' of type Int instance (Num a) => Num (NewNum a) where abs (NewNum a s) = NewNum (abs a) s --etc