title: Precomposing monad transformers
body: <p>Suppose I have two monad transformers</p>
  
  <pre><code>T1 :: (* -&gt; *) -&gt; * -&gt; *
  T2 :: (* -&gt; *) -&gt; * -&gt; *
  </code></pre>
  
  <p>with instances</p>
  
  <pre><code>instance MonadTrans T1
  instance MonadTrans T2
  </code></pre>
  
  <p>and some</p>
  
  <pre><code>X :: (((* -&gt; *) -&gt; * -&gt; *) -&gt; ((* -&gt; *) -&gt; * -&gt; *) -&gt; * -&gt; *)
  </code></pre>
  
  <p>such as</p>
  
  <pre><code>newtype X t1 t2 a b = X { x :: t1 (t2 a) b }
  </code></pre>
  
  <p>for which I would like to define something along the lines</p>
  
  <pre><code>instance (MonadTrans t1, MonadTrans t2) =&gt; MonadTrans (X t1 t2) where
      lift = X . lift . lift
  </code></pre>
  
  <p>so that I can use <code>lift</code> to lift <code>m a</code> into <code>X T1 T2 m a</code>?</p>
  
  <p>The problem here seems to be that the <code>lift</code>s act on some monad <code>Monad m =&gt; m a</code> which I cannot guarantee to be produce in the intermediate steps. But this is confusing for me. I am providing an implementation of <code>lift</code> so I can assume I have <code>Monad m =&gt; m a</code>, so I apply the rightmost <code>lift</code> and get <code>T1 m a</code> that I know nothing about, but shouldn't it be implied that <code>T1 m</code> is a <code>Monad</code>? If not why cannot I simply add this to the constraint of my instance</p>
  
  <pre><code>instance ( MonadTrans t1
           , MonadTrans t2
           , Monad (t2 m) ) =&gt; MonadTrans (X t1 t2) where ...
  </code></pre>
  
  <p>This does not work either. I have an intuition that by the above I am saying "should there be <code>t1</code>, <code>t2</code>, <code>m</code> such that ..." which is too weak to prove that <code>X t1 t2</code> is a transformer (works for any/all <code>Monad m</code>). But it still doesn't make much sense to me, can a valid monad transformer produce a non-monad when applied to a monad? If not, I should be able to get away with the instance of <code>MonadTrans (X t1 t2)</code>.</p>
  
  <p>Is there a trick to do it that just eludes me or is there a reason why it cannot be done (theoretical or a limitation of what current compilers support).</p>
  
  <p>Would the implication correspond to anything other than</p>
  
  <pre><code>instance (MonadTrans t, Monad m) =&gt; Monad (t m) where
      return  = lift . return
      a &gt;&gt;= b = ... # no sensible generic implementation
  </code></pre>
  
  <p>which would overlap other instances / could not provide the specific bind? Couldn't this be worked around with some indirection? Making <code>returnT :: Monad m =&gt; a -&gt; t m a</code> and <code>bindT :: Monad m =&gt; t m a -&gt; (a -&gt; t m b) -&gt; t m b</code> part of <code>MonadTrans</code> so that one can then write</p>
  
  <pre><code>instance MonadTrans (StateT s) where
      lift = ...
      returnT = ...
      bindT = ...
  
  ...
  
  instance (MonadTrans t, Monad m) =&gt; Monad (t m) where
      return  = returnT
      a &gt;&gt;= b = a `bindT` b
  </code></pre>
  
  <p>This kind of instances is not currently valid due to overlapping, would they however be feasible, useful?</p>