Partiality Monad Transformer

Question

I'm trying to deconstruct the IResult monad from attoparsec into a few pieces. Here's IResult

data IResult t r = Fail t [String] String
                 | Partial (t -> IResult t r)
                 | Done t r

This feels like it ought to be a combination of effects, "partiality" and failure. If failure is represented as just an Either ([String], String) then partiality might be

data Partiality t a = Now a | Later (t -> Partiality t a)

instance Monad (Partiality t) where
  return = pure
  (Now a) >>= f = f a
  (Later go) >>= f = Later $ \t -> go t >>= f

class MonadPartial t m where
  feed  :: t -> m a -> m a
  final :: m a -> Bool

instance MonadPartial t (Partiality t) where
  feed _ (Now a) = Now a
  feed t (Later go) = go t
  final (Now _) = True
  final (Later _) = False

(which gets its namesake from a paper by Danielsson when you use Partiality ())

I could use Partiality as a base monad, but is there a PartialityT monad transformer?

Answer 1

There sure is! Your Partiality monad is a free monad:

import Control.Monad.Free  -- from the `free` package

type Partiality t = Free ((->) t)

... and the corresponding PartialityT is a free monad transformer:

import Control.Monad.Trans.Free  -- also from the `free` package

type PartialityT t = FreeT ((->) t)

Here's an example program showing how you would use it:

import Control.Monad
import Control.Monad.Trans.Class
import Control.Monad.Trans.Free

type PartialityT t = FreeT ((->) t)

await :: (Monad m) => PartialityT t m t
await = liftF id

printer :: (Show a) => PartialityT a IO r
printer = forever $ do
    a <- await
    lift $ print a

runPartialityT :: (Monad m) => [a] -> PartialityT a m r -> m ()
runPartialityT as p = case as of
    []   -> return ()
    a:as -> do
        x <- runFreeT p
        case x of
            Pure _ -> return ()
            Free k -> runPartialityT as (k a)

We build the free monad transformer using the await command to request new values and lift to invoke actions in the base monad. We get the Monad and MonadTrans instances for PartialityT for free, because the free monad transformer is automatically a monad and monad transformer for any given functor.

We run the above program like so:

>>> runPartialityT [1..] printer
1
2
3
...

I recommend you read this post I wrote about free monad transformers. However, the new official home of the free monad transformer is the free package.

Also, if you are looking for an effectful incremental parser, I'm about to release that as the pipes-parse package within a few days. You can check the current draft here.