I have a situation where I want to interleave a free monadic DSL with state, but interpret the state mid-program. Below is a simplified example with only logging and state. More generally the problem is that we need to perform some effects to obtain the initial state, so it can't be done during the final interpretation (runProgram below). Using tagless final and StateT this is simple. The same is probably true using an extensible effect system like polysemy. I couldn't figure out how to do this using coproducts from Data types à la carte while only interpreting part of the union. Perhaps there's an elegant way using coproducts.

I decided to try using FreeT after seeing similar examples here in Haskell and here in Scala. However, the situation is slightly different: the base monad is their custom DSL, rather than some state monad. As far as I can tell, I need state to be the base in order to be able to “eliminate” it in the middle of the program.

Here’s my broken attempt (full example in this gist):

runProgram :: IO ()
runProgram = iterM interpret program

data Log next = Log String next | Noop next deriving Functor

-- Might be the problem, applicative instance using dummy constructor needed for iterT
instance Applicative Log where pure = Noop

type Program a = FreeT (State Int) (Free Log) a

myLog :: String -> Free Log ()
myLog s = liftF $ Log s ()

interpret :: Log (IO a) -> IO a
interpret = \case
  Log s next -> putStrLn s >> next
  Noop next  -> next

-- Program with only logging, state interpreted in the middle
program :: Free Log ()
program = do
  myLog "Before stateful program"
  finalState <- eliminateState 3 statefulProgram
  myLog $ "Final state: "    show finalState

eliminateState :: Int -> Program Int -> Free Log Int
eliminateState initialState = iterT (`evalState` initialState)

-- Combines logging and state, but the state doesn't stick. Why?
statefulProgram :: Program Int
statefulProgram = do
  lift $ myLog "In stateful program, modifying state"
  liftF $ modify ( 1)
  updatedState <- liftF get
  lift $ myLog ("In stateful program, updated state is: "    show updatedState)
  return updatedState

The state doesn't stick here, output is:

Before stateful program
In stateful program, modifying state
In stateful program, updated state is: 3
Final state: 3

I suspect there's something fundamentally not sound with this approach and that the bodged together DSL Applicative instance is a symptom of that. But I'm not sure what it is. So two questions:

1. What is the problem with this particular implementation?
2. How can this situation be modeled using free monads?

CodePudding user response：

As for

What is the problem with this particular implementation?

The FreeT monad transformer is like an onion, with multiple nested layers of the functor parameter (here, State Int).

The function that is passed to iterT is used to "peel" the functorial layers. The problem is that there's no communication between the successive State Int layers. (`evalState` initialState) is used to run each layer separately, always with the same initial state, always discarding the final state for the layer, as evalState is wont to do.

CodePudding user response：

Answering the narrow question (from your comment) of how to write the handler for StateF. (I’m on my phone, so I’ve only type checked this code in my head, but it should give you the general idea.)

data StateF s a = Get (s -> a) | Put s a
data (f : : g) a = L (f a) | R (g a)

runState :: s -> Free (StateF : : f) a -> Free f (a, s)
runState s (Pure x) = return (x, s)
runState s (Free (L (Get k))) = runState s (k s)
runState _ (Free (L (Put s m))) = runState s m
runState s (Free (R f)) = Free (runState s <$> f)

In the R case, you want to leave this layer of the free monad intact (it’s some unknown non-StateF effect). So we just recursively run the rest of the computation inside the f functor using <$>.

You could probably write this code using iter(M), if you don’t like the explicit recursion, but I think you’d need to use StateT to do that.