haskellrecursionmonadsmonad-transformersfree-monad

How to make a free monad interpreter recursive?


In a Free monad interpreter using iterT, I'd like to have an internal state, but I'm not sure how to do so since the iterT function provides the continuation f pre-loaded with the recursive call, as I understand it. I suppose a StateT wrapper is a possible solution (?) but it would be nice to avoid if possible. Thanks.

Edit: To clarify, the internal state is the mval parameter passed to the inner func. I'd like to allocate a resource and continue the interpreter with the resource.

import Control.Monad.Trans.Free.Church
import Control.Monad.Free.TH

type SomeFree m = FT SomeFreeF m
data SomeFreeF next = SomeAct (() -> next)
deriving instance (Functor SomeFreeF)
makeFree ''SomeFreeF

runSomeFree :: SomeFree IO () -> IO ()
runSomeFree = inner Nothing
  where
  inner mval =
    iterT \case
      SomeAct f -> do
        case mval of
          Nothing -> do
            a <- init
            inner (Just a) (FT someAct f ??)
                       -- How to continue the inner loop with    
                       -- the new state and the continuation `f`?
          Just a -> do
            f a

Solution

  • As I noted in the comments, at first blush this seems like a job for iterTM, which is like iterT except it runs in the monad transformer of your choice.

    iterTM :: (Functor f, Monad m, MonadTrans t, Monad (t m)) => (f (t m a) -> t m a) -> FreeT f m a -> t m a
    iterTM f (FreeT m) = do  -- running in the output monad `t`
        val <- lift m
        case fmap (iterTM f) val of  -- fold the children first
            Pure x -> return x
            Free y -> f y
    

    You get to pick the output monad t, but m and a are defined by the FreeT data structure you're folding up. For each layer of the FreeT, starting at the bottom, iterTM passes an f full of the results of folding the layer's children into your callback. You get to decide how to process those monadic results (pick between them, sequence them, whatever).

    You mentioned running your fold in a StateT, but the example code you've given looks more like ReaderT to me. (You're not returning a modified state from each iteration - just passing a modified parameter downwards.)

    runSomeFree :: Monad m => SomeFree m a -> ReaderT (Maybe ()) m a
    runSomeFree = iterTM go
        where
            go (SomeAct f) = ask >>= \case
                Just () -> f ()
                Nothing -> local (const $ Just ()) (f ())