How to nest Parser (IO a) while avoiding unsafePerformIO?

Question

While playing around with parsing based on text-icu's BreakIterator, I've got stuck on implementing a function like this

conditionalParser :: (a -> Bool) -> Parser a -> Parser a -> Parser a -> Parser a
conditionalParser f a b c = do
        a' <- a
        if f a'
                then b
                else c

but with a type

conditionalParserIO :: (a -> Bool) -> Parser (IO a) -> Parser (IO a) -> Parser (IO a) -> Parser (IO a)

Is it possible without doing unsafePerformIO?

So far I could only get to some nested dos with the final returned type being Parser (IO (Parser (IO a))), but without any idea how to collapse them.

Answer 1

I think what you want is to use ParsecT instead of Parser.

conditionalParserM :: Monad m => (a -> Bool) -> ParsecT s u m a -> ParsecT s u m a -> ParsecT s u m a
conditionalParserM f a b c = do
    a' <- a
    if f a' then b else c

This function works with all types of Monads, not just IO.

I suppose it's possible to convert from a ParsecT s u IO a to a Parser (IO a) using runParsecT, depending on which Parser (this or this?) you're using. However, I would recommend that you just restructure your code to work with ParsecT instead.

---

Clarification

conditionalParserM can't be used as a replacement for conditionalParserIO. I'm suggesting that you need to change how your program works, because attempting to do what your doing (without unsafePerformIO, which you should almost never use) is impossible.

You're looking to compose parsers based on the result of an IO operation, which means that the parser itself will perform side effects when it is run. In order to encapsulate this in the type, you need to use a monad transformer instead.

So, to use conditionalParserM, you need to restructure your code to work with ParsecT instead of Parser.

Answer 2

I just wanted to comment on the difference between Parsec s u (IO a) and ParsecT s u IO a.

You correctly observed that trying to implement your function using Parsec (IO a) yields to Parser (IO (Parser (IO a)). Since both Parser and IO are monads, for both of them we have join :: m (m a) -> m a, which allows to collapse double Parser or double IO. However, in our results we have IO and Parser interleaved. What we need is some function of type IO (Parser a) -> Parser (IO a). If we had such a function f and some x :: Parser (IO (Parser (IO a)), we could use it as liftM f x :: Parser (Parser (IO (IO a))) and then use join and liftM join to collapse both parts into desired Parser (IO a).

Unfortunately there is no such general function for swapping two monads. It's not possible to construct such a function without knowing the internals of a monad, and for some monads it's not even possible at all. For example, there is no total function of type (a -> Maybe b) -> Maybe (a -> b) (the first monad being Maybe, the second one the reader monad (->) a).

And this is why we have monad transformers. A monad transformer corresponding to some monad M knows how to interleave M with another monad. For some monads, such as Reader, swapping it with another monad in the above manner is possible and its transformer is doing exactly that. ReaderT r m a is defined as r -> m a and we can construct:

import Control.Monad
import Control.Monad.Trans
import Control.Monad.Trans.Reader

swapReader :: (Monad m) => m (Reader r a) -> Reader r (m a)
swapReader = fromReaderT . join . lift . liftM (toReaderT . liftM return)
  where
    -- Helpers to convert ReaderT to Reader and back
    fromReaderT :: (Monad m) => ReaderT r m a -> Reader r (m a)
    fromReaderT = reader . runReaderT
    toReaderT :: (Monad m) => Reader r (m a) -> ReaderT r m a
    toReaderT = ReaderT . runReader

We convert m (Reader r a) into ReaderT r m (ReaderT r m a) by augmenting both the inner and outer part and then just collapse it using join.

For other monads, such as MaybeT, swapping is impossible (as in the example above with the (->) a monad). So their transformers are defined differently, for example MaybeT m a is defined as m (Maybe a), not Maybe (m a). Therefore ReaderT r Maybe a is isomorphic MaybeT (ReaderT r) a! There is just one sensible way how to combine Reader and Maybe and so both transformers result in the same thing.

Luckily, we don't have to care about this stuff, once somebody defines a transformer for us. All we need to know is that the laws hold and how to run the transformer stack at the end.

So using ParsecT s u IO a is the proper solution. ParsecT knows how to interleave parsing within another monad and allows you to combine operations from both of them, without having to deal with the internals.