Tying the Knot with a State monad

Question

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 `do rec` block. I have this working, and kinda-sorta-reasonably abstracted into a `StateT`-esque monad transformer: ``` {-# 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 -> Knot s -> m (a, Knot s) runRecStateT (RecStateT st) = S.runStateT st tie :: MonadFix m => RecStateT s m a -> s -> m (a, s) tie m s = do rec (a, Knot s' _) <- runRecState…

Accepted Answer

I've been playing around with stuff, and I think I've come up with something... interesting. I call it the "Seer" monad, and it provides (aside from Monad operations) two primitive operations:

```
see  :: Monoid s => Seer s s
send :: Monoid s => s -> Seer s ()
```

and a run operation:

```
runSeer :: Monoid s => Seer s a -> a
```

The way this monad works is that `see` allows a seer to see everything, and `send` allows a seer to "send" information to all other seers for them to see. Whenever any seer performs the `see` operation, they are able to see all of the information that has been sent, and all of the information that will be sent. In other words, within a given run, `see` will always produce the same result no matter where or when you call it. Another way of saying it is that `see` is how you get a working reference to the "tied" knot.

This is actually very similar to just using `fix`, except that all of the sub-parts are added incrementally and implicitly, rather than explicitly. Obviously, seers will not work correctly in the presence of a paradox, and sufficient laziness is required. For example, `see >>= send` may cause an explosion of information, trapping you in a time loop.

A dumb example:

```
import Control.Seer
import qualified Data.Map as M
import Data.Map (Map, (!))

bar :: Seer (Map Int Char) String
bar = do
  m <- see
  send (M.singleton 1 $ succ (m ! 2))
  send (M.singleton 2 'c')
  return [m ! 1, m ! 2]
```

As I said, I've just been toying around, so I have no idea if this is any better than what you've got, or if it's any good at all! But it's nifty, and relevant, and if your "knot" state is a `Monoid`, then it just might be useful to you. Fair warning: I built `Seer` by using a `Tardis`.

https://github.com/DanBurton/tardis/blob/master/Control/Seer.hs

Tying the Knot with a State monad

Solution

Problem

Related problems