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
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