title: Monad Stack Penetration Classes with Free/Operational Monad Transformers?
body: <p>Can there be mtl-like mechanism for monad transformers created by FreeT / ProgramT ?</p>
  
  <p>My understanding of the history is as follows. Once upon a time monad transformer was invented. Then people started to stack monad transformers one on other, then found it annoying to insert <code>lift</code> everywhere. Then a couple of people invented monad classes, so that we can e.g. <code>ask :: m r</code> in any monad <code>m</code> such that <code>MonadReader r m</code> . This was possible by making every monad class <em>penetrate</em> every monad transformer, like</p>
  
  <blockquote>
    <p><code>(Monoid w, MonadState s m) =&gt; MonadState s (WriterT w m)<br>
    MonadWriter w m =&gt; MonadWriter w (StateT s m)</code></p>
  </blockquote>
  
  <p>you need such pair of instance declarations for every pair of monad transformers, so when there's <em>n</em> monad transformers there's <em>n</em>^2 costs. This was not a large problem, however, because people will mostly use predefined monads and rarely create their own. The story so far I understand, and also is detailed e.g. in the following Q&amp;A:</p>
  
  <p><a href="https://stackoverflow.com/questions/9054731/avoiding-lift-with-monad-transformers">Avoiding lift with Monad Transformers</a></p>
  
  <p>Then my problem is with the new Free monads <a href="http://hackage.haskell.org/package/free" rel="nofollow noreferrer">http://hackage.haskell.org/package/free</a> and Operational monads <a href="http://hackage.haskell.org/package/operational" rel="nofollow noreferrer">http://hackage.haskell.org/package/operational</a> . They allow us to write our own DSL and use it as monads, just by defining the language as some algebraic <code>data</code> type (Operational doesn't even need <code>Functor</code> instances). Good news is that we can have monads and monad transformers for free; then how about monad classes? Bad news is that the assumption "we rarely define our own monad transformers" no longer holds.</p>
  
  <p>As an attempt to understand this problem, I made two <code>ProgramT</code>s and made them penetrate each other;</p>
  
  <p><a href="https://github.com/nushio3/practice/blob/master/operational/exe-src/test-05.hs" rel="nofollow noreferrer">https://github.com/nushio3/practice/blob/master/operational/exe-src/test-05.hs</a></p>
  
  <p>The <code>operational</code> package does not support monad classes so I took another implementation <code>minioperational</code> and modified it to work as I need; <a href="https://github.com/nushio3/minioperational" rel="nofollow noreferrer">https://github.com/nushio3/minioperational</a></p>
  
  <p>Still, I needed the specialized instance declaration</p>
  
  <blockquote>
    <p><code>instance (Monad m, Operational ILang m) =&gt; Operational ILang (ProgramT SLang m) where</code></p>
  </blockquote>
  
  <p>because the general declaration of the following form leads to undecidable instances.</p>
  
  <blockquote>
    <p><code>instance (Monad m, Operational f m) =&gt; Operational f (ProgramT g m) where</code></p>
  </blockquote>
  
  <p>My question is that how can we make it easier to let our Operational monads penetrate each other. Or, is my wish to have penetration for any Operational monad ill-posed.</p>
  
  <p>I'd also like to know the correct technical term for <em>penetration</em> :)</p>