Proposal: Applicative => Monad: Call for consensus

[Jan-Willem Maessen]

I should mention Re: the original topic of discussion that I'm
actually a class completist, and was roundly shouted down and told to
use RULEs when I suggested moving a method into a class for efficiency
purposes (no, don't remember quite what function in question
was---except that it actually improved asymptotic complexity, which I
thought was pretty compelling at the time).

But I originally chimed in to the side conversation about whether >>=
or join is more natural when explaining monads computationally (as
opposed to mathematically) and thus when writing code intended to be
read (as all good code should).

I think Tyson Whitehead unwittingly made my point rather well using
the example of the CPS monad.  I believe his simple explanation of
join in CPS actually leads to an incorrect definition, whereas
explaining >>= in CPS is about as straightforward as anything
involving CPS can be (which is to say, more than a little convoluted).

On Mon, Jan 17, 2011 at 12:22 PM, Tyson Whitehead <twhitehead at gmail.com> wrote:
> On January 15, 2011 22:43:32 Jan-Willem Maessen wrote:
>> For example, I find it relatively easy to
>> understand >>= in the continuation monad, but have to spend a long
>> time puzzling my way through join.
>
> It's not that bad once you get used to thinking of it.  Join simply merges an
> inner computation into an outer one.

Sure, I understand this much.  And I argued that it was hard to think
about CPS in terms of fmap and join, so you argued otherwise:

>...
> Join allows you to merge the C1--C2--C3 dynamically determined from A--B--C
> into the continuation passing string to get
>
> A--B--C--C1--C2--C3--D--E ...  (C1--C2--C3 is determined by A--B--C)
>
> This is actually relatively clear from join's type
>
> join :: Monad m => m (m a) -> m a
>
> It takes a string of computations (as indicated by the outer m) that generates
> a string of computations generating an a (as indicated by the inner m a).  It
> changes this into just a string of computations generating an a.
>
> How can it do this?  It must set things up to first run the given string of
> computations in order to determine the string of computations that give a.
> Once it gets this, it must then run it in order to get a.
>
> join (CPS f) = CPS $ \k -> unCPS (f id) k
>
> That is, when invoked (i.e., when given a continuation k), invoke f with the
> continuation id.  This will cause f to return the inner computation it
> computes.  Then invoke this returned computation by passing it k.

Except that I believe this definition is incorrect, as it introduces a
fresh continuation (id) that is not constructed from k!  Moreover, it
begs the question of how the mechanics of continuation-passing are
accomplished.  Here's a rather natural definition of the CPS monad,
written from the top of my head:

return x = CPS (\k -> k x)

CPS ca >>= fb = CPS (\k -> ca (\a -> unCPS (fb a) k))

Here we have a computation returning an a (ca), and we construct a
continuation to pass to it that receives the a and passes it on to fb,
then passes our continuation on to that.  It lays bare the essence of
continuation passing (well, we might need to erase the CPS/unCPS
operations to make it really clear, but it's reasonably easy to
convey).

Using these definitions, and join = (>>= id), we obtain:

join (CPS cca) = CPS (\k -> cca (\ca -> unCPS ca k))

That is, we construct a fresh continuation that we pass to cca, that
receives the computation ca returning an a, and invokes ca with
continuation k.  I believe this is rather different from your
definition, as the type of the continuation that we pass to cca is
(say)  a -> r  in the above definition, but is a -> a in yours.

I derived >>= in terms of your definition of join, as well, but it's
rather unenlightening.  I think the resulting monad might be
isomorphic to the Identity, but I'm pretty sure call/cc doesn't really
do anything.

-Jan-Willem Maessen