MonadFix instance for interpreter monad transformer generated by FreeT?

Question

I have a simplified version of the standard interpreter monad transformer generated by FreeT:

data InteractiveF p r a = Interact p (r -> a)

type Interactive p r = FreeT (InteractiveF p r)

p is the "prompt", and r is the "environment"...one would run this using something like:

runInteractive :: Monad m => (p -> m r) -> Interactive p r m a -> m a
runInteractive prompt iact = do
  ran <- runFreeT iact
  case ran of
    Pure x -> return x
    Free (Interact p f) -> do
      response <- prompt p
      runInteractive prompt (f resp)

instance MonadFix m => MonadFix (FreeT (InteractiveF p r)) m a)
mfix = -- ???

I feel like this type is more or less just a constrained version of StateT...if anything, an Interactive p r IO is I think a constrained version of IO...I think...but... well, in any case, my intuiton says that there should be a good instance.

I tried writing one but I can't really seem to figure out. My closest attempt so far has been:

mfix f = FreeT (mfix (runFreeT . f . breakdown))
  where
    breakdown :: FreeF (InteractiveF p r) a (FreeT (InteractiveF p r) m a) -> a
    breakdown (Pure x) = x
    breakdown (Free (Interact p r)) = -- ...?

I also tried using a version taking advantage of the MonadFix instance of the m, but also no luck --

mfix f = FreeT $ do
  rec ran <- runFreeT (f z)
      z   <- case ran of
               Pure x -> return x
               Free iact -> -- ...
  return -- ...

Anyone know if this is really possible at all, or why it isn't? If it is, what's a good place for me to keep on looking?

---

Alternatively, in my actual application, I don't even really need to use FreeT...I can just use Free; that is, have Interactive be just a monad and not just a monad transformer, and have

runInteractive :: Monad m => (p -> m r) -> Interactive p r a -> m a
runInteractive _ (Pure x) = return x
runInteractive prompt (Free (Interact p f) = do
    response <- prompt p
    runInteractive prompt (f response)

If something is possible for this case and not for the general FreeT case, I would also be happy :)

Answer 1

Imagine you already had an interpreter for Interactive.

interpret :: FreeT (InteractiveF p r) m a -> m a
interpret = undefined

It would be trivial to write a MonadFix instance:

instance MonadFix m => MonadFix (FreeT (InteractiveF p r) m) where
    mfix = lift . mfix . (interpret .)

We can directly capture this idea of "knowing the interpeter" without committing to an interpreter ahead of time.

{-# LANGUAGE RankNTypes #-}

data UnFreeT t m a = UnFree {runUnFreeT :: (forall x. t m x -> m x) -> t m a}
--   given an interpreter from `t m` to `m` ^                          |
--                                  we have a value in `t m` of type a ^

UnFreeT is just a ReaderT that reads the interpreter.

If t is a monad transformer, UnFreeT t is also a monad transformer. We can easily build an UnFreeT from a computation that doesn't require knowing the interpreter simply by ignoring the interpeter.

unfree :: t m a -> UnFreeT t m a
--unfree = UnFree . const
unfree x = UnFree $ \_ -> x

instance (MonadTrans t) => MonadTrans (UnFreeT t) where
    lift = unfree . lift

If t is a monad transormer, m is a Monad, and t m is also a Monad, then UnFree t m is a Monad. Given an interpreter we can bind together two computations that require the interpeter.

{-# LANGUAGE FlexibleContexts #-}

refree :: (forall x. t m x -> m x) -> UnFreeT t m a -> t m a
-- refree = flip runUnFreeT
refree interpreter x = runUnFreeT x interpreter

instance (MonadTrans t, Monad m, Monad (t m)) => Monad (UnFreeT t m) where
    return = lift . return
    x >>= k = UnFree $ \interpreter -> runUnFreeT x interpreter >>= refree interpreter . k

Finally, given the interpreter, we can fix computations as long as the underlying monad has a MonadFix instance.

instance (MonadTrans t, MonadFix m, Monad (t m)) => MonadFix (UnFreeT t m) where
    mfix f = UnFree $ \interpreter -> lift . mfix $ interpreter . refree interpreter . f

We can actually do anything the underlying monad can do, once we have the interpreter. This is because, once we have an interpreter :: forall x. t m x -> m x we can do all of the following. We can go from m x through t m x all the way up to UnFreeT t m x and back down again.

                      forall x.
lift               ::           m x ->         t m x
unfree             ::         t m x -> UnFreeT t m x
refree interpreter :: UnFreeT t m x ->         t m x
interpreter        ::         t m x ->           m x

Usage

For your Interactive, you'd wrap the FreeT in UnFreeT.

type Interactive p r = UnFreeT (FreeT (InteractiveF p r))

Your interpreters would still be written to produce a FreeT (InteractiveF p r) m a -> m a. To interpret the new Interactive p r m a all the way to an m a you'd use

interpreter . refree interpreter

The UnFreeT no longer "frees the interpreter as much as possible". The interpreter can no longer make arbitrary decisions about what to do wherever it wants. The computation in UnFreeT can beg for an interpreter. When the computation begs for and uses an interpreter, the same interpreter will be used to interpret that portion of the program as was used to start interpreting the program.