[Haskell-cafe] Re: Parsers are monadic?

apfelmus apfelmus at quantentunnel.de
Mon Jul 2 07:01:55 EDT 2007

Paul Hudak wrote:
>    readFile :: Name -> FailCont -> StrCont -> Behaviour
> Here StrCont was the success continuation, which took a string (the file
> contents) as argument.  I rather liked the flexibility that this offered
> -- since I/O errors were fairly common, it made sense to give success
> and failure equal status.

> Claus Reinke wrote:
>> contrary to monadic parsers, those continuation-based parsers
>> had *two* continuations, one for success, one for failure. and
>> that seemed to be a very natural match for the problem.

In a sense, the MonadError class

  class Monad m => MonadError e m | m -> e where
    throwError :: e -> m a
    catchError :: m a -> (e -> m a) -> m a

defines a second monad structure, with

    return = throwError
    bind   = catchError

To make this apparent and symmetric, let's define a

  class DiMonad m where
    returnR :: a -> m e a
    bindR   :: m e a -> (a -> m e b)  -> m e b

    returnL :: e -> m e a
    bindL   :: m e a -> (e -> m e' a) -> m e' a

A dimonad  m e a  can be thought of as a monad  m e  with a variable
error type  e . The operations with suffixed by R are the "normal" monad
operations whereas the suffix L marks the "error"-catching operations.
(Question: can dimonads solve the extensible-exceptions problem?)

Now, the two-continuation approach always requires to pass two
continuations. But here, returnL and returnR only pass the failure- or
the success-continuation. To see what's happening, let's turn

  type TwoCont e a = (e -> R) -> (a -> R) -> R

with some fixed result type R into a dimonad (for clarity, we ignore
that this is only a type-synonym):

  instance DiMonad TwoCont where
    returnR x = \e a -> a x
    bindR m f = \e a -> m e (\x -> (f x) e a)

    returnL y = \e a -> e y
    bindL m f = \e a -> m (\y -> (f y) e a) a

In the case of success-continuation, this means that the dimonad passes
one and the same error continuation, i.e. one and the same
exception-handler will the thrown regardless of where the failure
happens inside a chain of actions composed with  bindR. Likewise,
error-handler and success-chain will be resumed at with a common
success-chain. Of course, this is well-known behavior for IO and
exceptions, and it seems that it reduces clutter quite well compared to
a bare TwoCont.

A final question remains: does the dimonad abstraction cover the full
power of TwoCont? I mean, it still seems like there's an operation
missing that supplies new left and right continuations at once.


More information about the Haskell-Cafe mailing list