# Proposal: Applicative => Monad: Call for consensus

Tue Jan 18 19:09:41 CET 2011

```On January 17, 2011 19:24:12 Jan-Willem Maessen wrote:
> > 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.

You guys are both right.  It shouldn't be any reflection on join or the
description I gave for it though.  I simply screwed up by lifting operations
out of the continuation without thinking about preserving callCC.

Let me restate the last little bit of the above.

---
join (CPS f) = CPS \$ \k -> f (g -> unCPS g k)

That is, when invoked (i.e., when given a continuation k), invoke f with a
continuation that takes the computation g generated by f and invokes it next
by passing it k.
---

My mistake in simplifying this expression was assuming f ends with returning
unCPS k0 k1 (letting me lift the unCPS transformation and application of k1
out of the lambda giving id).  callCC allows f to not end with unCPS k0 k1.

The net effect of lifting these operations out was that it stops f from being
able to discard them (i.e., escape past the join).  Well subtle, I'm not sure
it was too subtle.  It is pretty clearly reflected in the types

newtype Cont r a = CPS { unCPS :: (a -> r) -> r }

join :: Cont (Cont r a) (Cont r a) -> Cont r a
join (CPS f) = CPS \$ \k -> unCPS (f id) k

vs

join :: Cont r (Cont r a) -> Cont r a
join (CPS f) = CPS \$ \k -> f (g -> unCPS g k)

Cheers! -Tyson

PS:  I don't have anything against bind.  I just find join is also nice to have
for more functional/applicative style programming.  It is also conceptually