Proposal: Applicative => Monad: Call for consensus

[Tyson Whitehead]

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 
nice as it is quite clear about what additional complexity a monad gives you.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 490 bytes
Desc: This is a digitally signed message part.
URL: <http://www.haskell.org/pipermail/libraries/attachments/20110118/f9a09e55/attachment.pgp>