[Haskell-cafe] Re: Different choice operations in a continuation monad

[Heinrich Apfelmus]

Sebastian Fischer wrote:
> Heinrich Apfelmus wrote:
>>
>> 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.
> 
> <Aside>
> 
>> Personally, I recommend to stop thinking about continuations altogether
>> and instead use the approach I've outlined in "The Operational Monad
>> Tutorial"
> 
> I appreciate your operational monad tutorial both for the idea and how
> you explained it. But the advice "stop thinking about X because Y is
> better" feels odd to me. Before I know by myself that Y is better than X
> (which requires thinking about both X and Y) I don't feel comfortable
> following such advice. Afterwards, I don't need such advice ;)

Very true. :) My flimsy "personally" was an attempt to declare my
recommendation optional. I failed to say the right thing even then, for
I don't mean to stop thinking about continuations in general, just to
discourage them as foundation for implementing other monads.

> There may be more to X than just Y. IIRC, there is more to
> 'continuations' than 'monads'. For example, the implementation of
> `callCC` does not type check with your changed data type.

Ah, indeed,  callCC  in the operational setting is much trickier than I
thought. However, it also seems to be the reason why your original
approach does not work so well!

Basically, your choice of implementation

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

supplies a default semantics for  callCC . But this means that when
implementing  orElse , you also have to consider its interaction with
callCC , even when you actually don't want to expose or implement a
callCC  function.

As for the interaction: what should

  ((callCC ($ 0) >> mzero) `orElse` return 2) >>= return . (+3)

be? If the scope of  callCC  should not extend past  orElse , then this
evaluates to  return 5 . But this choice of scope dictates the type that
Holger mentioned.

If the the scope of  callCC  should extend beyond the  orElse , so that
the whole thing evaluates to  mzero ,  orElse  will have the type of
mplus . But then, I think that your implementation type  CMaybe  needs
to be more sophisticated because  orElse  now needs to detect whether
the argument contains a call to  callCC  or not in order to distinguish

  ((callCC ($ 0) >> mzero) `orElse` return 2) >>= return . (+3)

  ==> mzero

from

  (mzero `orElse` return 2) >>= return . (+3)

  ==> return 5


In short, the interaction between  orElse  and  callCC  is tricky, and
it would be unfortunate to be forced to consider it due to a premature
choice of implementation type. This can't happen with the operational
approach, because that one merely implements the "free" monad over a set
of operations.

> I shall try to implement a monad that supports two choice operations
> (one which fulfills the distributive law and one which satisfies the
> cancellation property) with the operational package.

The main task will probably be to figure out the interaction between
mplus  and  orElse , i.e. to consider what stuff like

   a `orElse` (b `mplus` c)

should evaluate to.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com