title: Tying the Knot with a State monad
body: <p>I'm working on a Haskell project that involves tying a big knot: I'm parsing a serialized representation of a graph, where each node is at some offset into the file, and may reference another node by its offset. So I need to build up a map from offsets to nodes while parsing, which I can feed back to myself in a <code>do rec</code> block.</p>
  
  <p>I have this working, and kinda-sorta-reasonably abstracted into a <code>StateT</code>-esque monad transformer:</p>
  
  <pre><code>{-# LANGUAGE DoRec, GeneralizedNewtypeDeriving #-}
  
  import qualified Control.Monad.State as S
  
  data Knot s = Knot { past :: s, future :: s }
  
  newtype RecStateT s m a = RecStateT (S.StateT (Knot s) m a) deriving
    ( Alternative
    , Applicative
    , Functor
    , Monad
    , MonadCont
    , MonadError e
    , MonadFix
    , MonadIO
    , MonadPlus
    , MonadReader r
    , MonadTrans
    , MonadWriter w )
  
  runRecStateT :: RecStateT s m a -&gt; Knot s -&gt; m (a, Knot s)
  runRecStateT (RecStateT st) = S.runStateT st
  
  tie :: MonadFix m =&gt; RecStateT s m a -&gt; s -&gt; m (a, s)
  tie m s = do
    rec (a, Knot s' _) &lt;- runRecStateT m (Knot s s')
    return (a, s')
  
  get :: Monad m =&gt; RecStateT s m (Knot s)
  get = RecStateT S.get
  
  put :: Monad m =&gt; s -&gt; RecStateT s m ()
  put s = RecStateT $ S.modify $ \ ~(Knot _ s') -&gt; Knot s s'
  </code></pre>
  
  <p>The <code>tie</code> function is where the magic happens: the call to <code>runRecStateT</code> produces a value and a state, which I feed it as its own future. Note that <code>get</code> allows you to read from both the past and future states, but <code>put</code> only allows you to modify the "present."</p>
  
  <p><strong>Question 1</strong>: Does this seem like a decent way to implement this knot-tying pattern in general? Or better still, has somebody implemented a general solution to this, that I overlooked when snooping through Hackage? I beat my head against the <code>Cont</code> monad for a while, since it seemed possibly more elegant (see <a href="https://stackoverflow.com/questions/10560124/using-cont-to-acquire-values-from-the-future-and-the-past">similar post</a> from Dan Burton), but I just couldn't work it out.</p>
  
  <p><strong>Totally subjective Question 2</strong>: I'm not totally thrilled with the way my calling code ends up looking:</p>
  
  <pre><code>do
    Knot past future &lt;- get
    let {- ... -} = past
        {- ... -} = future
        node = {- ... -}
    put $ {- ... -}
    return node
  </code></pre>
  
  <p>Implementation details here omitted, obviously, the important point being that I have to get the <code>past</code> and <code>future</code> state, pattern-match them <em>inside a let binding</em> (or explicitly make the previous pattern lazy) to extract whatever I care about, then build my node, update my state and finally return the node.  Seems unnecessarily verbose, and I particularly dislike how easy it is to accidentally make the pattern that extracts the <code>past</code> and <code>future</code> states strict. So, can anybody think of a nicer interface?</p>