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