Proposal: Applicative => Monad: Call for consensus
Tyson Whitehead
twhitehead at gmail.com
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
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>
More information about the Libraries
mailing list