The top-level story is that I am trying to create a monad that somehow records the "intermediate steps" of computation.

If it is only for knowing where things went wrong, isn't that what the Either monad is for? The semantics of (Either YourErrorType) is that it returns `Right result' when all steps went through, and `Left errmsg' from the first place where something went wrong. You'd have to define YourErrorType to incorporate the relevant error information. If you also want something like a call stack, i.e. a message like "computation failed in step 3 with message: foo" Then you need to stack a state transformer on top, e.g. StateT CallStack (Either YourErrorType) which decodes to CallStack -> Either YourErrorType (resultType,CallStack) An example using mtl transformers: import Control.Monad.State.Strict import Control.Monad.Except type CallStack = (Int,[String]) type YourErrorType = String type M a = StateT CallStack (Except YourError) a fancyFunc :: Show a => (a -> b) -> (a -> M b) fancyFunc f a = do (n,stack) <- get put (n+1,show a : stack) return b fancyMaybe :: Show a => (a -> Maybe b) -> (a -> M b) fancyMaybe f a = do (n,stack) <- get case (f a) of Nothing -> throwError $ "Failed at step "++(show n)++" on input "++(show a) Just b -> do put (n+1,show a : stack) return b runChainOfComputations = runStateT (1,[]) I once wrote a type 'ProvenienceT' which is a bit fancier than the above. It is a monadic EDSL and constructs a graph where nodes are (Markup of) intermediate steps of a computation and where edges are (user-supplied descriptions of) functions. It is inspired by the Javelin software of the 80s which pre-dates Excel spreadsheets. The result can be rendered as html. Can provide code if anyone is interested. Cheers, Olaf