CODEWITHSUNDEEP
haskellrecursionmonadsmonad-transformersfree-monad
Scott
Scott

Reputation: 4110

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

Upvotes: 2

Views: 313

Answers (2)

Scott
Scott

Reputation: 4110

I am accepting Benjamin's answer as the correct one since it is perhaps the simplest / best answer to the question, but I ended up finding that the FT monad didn't facilitate my use case(s) easily. However, operational and monad-skeleton do allow this use case quite easily, since they do not thread the interpreter through the bind function. The latter is additionally hilarious and fun to work with.

Upvotes: 0

Benjamin Hodgson
Benjamin Hodgson

Reputation: 44664

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 ())

Upvotes: 1

Related Questions