title: Transforming a Monad to trace failure in recursive monadic code
body: <p>I have a longish recursive function with many cases for all of the different data forms it can operate on. The return type of the function is a <code>Maybe</code>, where <code>Nothing</code> represents failure. The recursive call fails if any of its subcalls fail, so the computation in each case of the function is done in a do block.</p>
  
  <p>The implementation I have so far is definitely buggy, because I'm giving it input that should succeed, and it is failing, i.e. evaluating to <code>Nothing</code>. However, I cannot determine which subcall is evaluating to <code>Nothing</code>. To try to pinpoint where this happens, I want to trace all of the recursive calls. I had the idea that if I could insert a <code>trace</code> call into <code>Maybe</code>'s <code>bind</code> (that is, <code>(&gt;&gt;=)</code>), I wouldn't have to insert <code>trace</code> into all of the cases of the function.</p>
  
  <p>To implement this idea, I just copied the implementation of the <code>Maybe</code> type along with its <code>Monad</code> instance and modified it as I described: I inserted calls to <code>trace</code> in the bind function.</p>
  
  <pre><code>data TraceMaybe a =  TNothing | TJust a
    deriving (Eq, Ord, Show)
  
  tracet :: TraceMaybe a -&gt; TraceMaybe a
  tracet TNothing = trace "monad failed" TNothing
  tracet x        = trace "monad good" x
  
  instance  Monad TraceMaybe  where
      (TJust x) &gt;&gt;= k = tracet $ k x
      TNothing  &gt;&gt;= _ = TNothing
      (TJust _) &gt;&gt;  k = tracet k
      TNothing  &gt;&gt;  _ = TNothing
      return          = TJust
      fail m          = TNothing
  </code></pre>
  
  <p>Then I was mostly able to just change the return type of the big function, although I had to change some things where my code assumed that the <code>Monad</code> was actually <code>Maybe</code> (<code>catMaybes</code>, for example), </p>
  
  <p>My question is this: is there a more elegant, compositional way to create an only slightly modified version of Maybe? I've heard of "<code>Monad</code> transformers", but the examples I've seen don't seem entirely relevant.</p>
  
  <p>I wonder if there is some way to combine Writer and Maybe to do this.</p>