3

I was writing some Haskell earlier today. Came up with something along the lines of

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype Foo a = Foo { ParsecT String () (Writer DefinitelyAMonoid) a }
    deriving (Functor, Applicative, Monad, MonadWriter DefinitelyAMonoid)

This did not compile. "No instance for (MonadWriter DefinitelyAMonoid (ParsecT String () (Writer DefinitelyAMonoid))) arising from the 'deriving' clause of a data type declaration", GHC told me. So I decided to see if some other MTL classes would work, and they did. Reader and MonadReader, and Writer and MonadWriter. So I turned was directed by a Discord user to Hackage, where the problem was clear:

MonadState  s m => MonadState  s (ParsecT s' u m)
MonadReader r m => MonadReader r (ParsecT s  u m)
MonadError  e m => MonadError  e (ParsecT s  u m)

No MonadWriter instance can make it through the ParsecT transformer! Seemed for all the world to me like a mere oversight, and I just barely realized before opening an issue on Github that this might be deliberate. So I took a look at Megaparsec:

(Stream s, MonadState st m) => MonadState st (ParsecT e s m)
(Stream s, MonadReader r m) => MonadReader r (ParsecT e s m)
(Stream s, MonadError e' m) => MonadError e' (ParsecT e s m)

Again, no MonadWriter.

Why do neither Parsec nor Megaparsec provide a MonadWriter instance for ParsecT? Is there something special about parser monads like these that keep them from playing nice with writers? Is there something similar to this going on?

Khuldraeseth na'Barya
  • 720
  • 1
  • 7
  • 30

1 Answers1

7

Parsec is a backtracking monad. While the MonadWriter instance you propose is not impossible, it's a strange thing to put a Writer underneath a backtracking monad. This is because the inner layers of a monad stack provide the "foundational" effects upon which the outer layers build -- that is, whatever ParsecT u (Writer w) does, it must do so only in terms of tell. So if it tells a value in a branch that is later backtracked out of, there is no possibility to "untell" that value, and so the Writer's result will be more like a trace of the parsing algorithm rather than a trace of the dataflow abstraction that Parsec is presenting. It's not useless, but it's pretty odd, and you would have much more natural semantics if WriterT were on the outside and Parsec on the inside.

The same argument applies to State. Parsec exposes both its own user state functionality (the u parameter) and a MonadState instance that inherits the underlying monad's state functionality. The latter comes with the same caveats as MonadWriter -- the statefulness follows the trace of the algorithm, not the dataflow. I don't know why this instance was included while the Writer instance was not; they are both tricky in the same way.

-- I'm presuming the user might want a separate, non-backtracking
-- state aside from the Parsec user state.
instance (MonadState s m) => MonadState s (ParsecT s' u m) where
    get = lift get
    put = lift . put

Parsec's user state, on the other hand, follows the dataflow, not computation, and it has the same effect as putting StateT on the outside. It always seemed odd that Parsec provides its own state facility rather than just asking us to use a transformer -- but, thinking about it now, I suspect it is just to avoid having to put lift all over the place if you do happen to use state.

In conclusion, they could provide the MonadWriter instance you ask for, but I think there is a decent reason not to -- to discourage making the mistake that I think you are probably making.

luqui
  • 59,485
  • 12
  • 145
  • 204