[Haskell-cafe] Speed of Error handling with Continuations vs. Eithers

[Derek Elkins]

On Sat, May 15, 2010 at 2:28 PM, Max Cantor <mxcantor at gmail.com> wrote:
> Where is my bind statement doing a case analysis? Isn't it just propagating, in a sense, the case analysis that came from values coming into the monad via return or via throwError?

What you did was reimplement the Either -type- not the Either -monad-.
 To see this lets make a complete interface to Either and provide the
two implementations of that, now, abstract data type.

Every function using Either can be written using the following interface:
class EitherLike e where
    injLeft :: a -> e a b
    injRight :: b -> e a b
    either :: (a -> c) -> (b -> c) -> e a b -> c

And here are two implementations:
instance EitherLike Either where
    injLeft = Left
    injRight = Right
    either = Prelude.either

type CEEither a b = forall c. (a -> c) -> (b -> c) -> c

instance EitherLike CEEither where
    injLeft a = \l r -> l a
    injRight b = \l r -> r b
    either f g e = e f g

Now we can write your functions and the "standard" Either monad
definitions in terms of this abstract interface.

> retErrCPS ::  a -> ErrCPS e m a
> retErrCPS x = ErrCPS $ \_ good -> good x

return x = Right x

retEither x = injRight x

retErrCPS x = ErrCPS $ injRight x

> bindErrCPS ::  ErrCPS e m b -> (b -> ErrCPS e m a) -> ErrCPS e m a
> bindErrCPS m f =  ErrCPS $ \err good -> runErrCPS m err $ \x -> runErrCPS (f x) err good

bindErrCPS m f = ErrCPS $ either injLeft (runErrCPS . f) (runErrCPS m)

Left e >>= _ = Left e
Right a >>= f = f a

bindEither m f = either injLeft f m

So, modulo wrapping and unwrapping, the code is identical.  In version
of GHC prior to pointer tagging, a case analysis on Either would be
implemented very much like the Church-encoded eliminator, i.e. in case
e of Left a -> f a, Right b -> g b pre-pointer tagging GHC would push
(essentially) f and g on a stack and enter e, e would then choose
which of f or g to return to.  So your representation is still doing a
case analysis, it is just representing it a different way.

> Also, why wouldn't callCC work here?  I'm not that familiar with the ContT monad so any more details would be very much appreciated.

It's hard to implement a "global" abort with callCC.  You can
implement a local one easily by using an outer callCC to provide an
"escape" continuation, but you have to explicitly pass around this
"escape" continuation.