Nice, the traceM here would help reduce the "hunt for a place to tack
the trace" game.
As an aside, I have the following defined, which I use much more
frequently than plain trace:
tracem msg x = Trace.trace ("**" ++ msg ++ ": " ++ show x) x
The 'm' has nothing to do with monads, it's just a short name.