On Wed, Jun 16, 2010 at 9:11 AM, Sebastian Fischer <sebf@informatik.uni-kiel.de> wrote:

Heinrich Apfelmus wrote:

Sebastian Fischer wrote:
I still don't understand why it is impossible to provide `orElse` with
the original type. I will think more about the reason you gave.

The reason is that you have chosen the "wrong" type for your
continuation monad; it should be

 newtype CMaybe a = CMaybe (forall r. (a -> Maybe r) -> Maybe r)

Yes, with this type `orElse` has the same type as `mplus`, which is very nice.

This type is the same as "Codensity Maybe" using category-extras which is a 'bit bigger than Maybe'. (To see why, figure out how Codensity Reader is isomorphic to State!) This is the wiggle room you're using to get the distributive operator.

Another encoding of Maybe is through Yoneda Endo

newtype YEMaybe a = YEMaybe (forall r. (a -> r) -> r -> r)

and it is isomorphic to the original Maybe type, with its same limitations. A definition that is equivalent to this is in my monad-ran package, along with definitions CPS/right-kan-extension-based definitions for other common monads, including the MTL, IO, ST s, and STM.

-Edward Kmett