[Haskell-cafe] Speed of Error handling with Continuations vs.
Eithers
Derek Elkins
derek.a.elkins at gmail.com
Sat May 15 16:21:04 EDT 2010
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.
More information about the Haskell-Cafe
mailing list