CODEWITHSUNDEEP
haskellmonadscontinuations
Babra Cunningham
Babra Cunningham

Reputation: 2967

Poor mans concurrency, understanding the monad instance?

I'm running through this guide to implementing concurrency and I'm having trouble understanding this monad instance:

data Action m = Atom (m (Action m)) | Fork (Action m) (Action m) | Stop

newtype C m a = C {apply :: (a -> Action m) -> Action m}

instance Monad (C m ) where
 m >>= f         = C $ \k -> apply m(\a -> apply (f a) k) --?
 return x        = C $ \k -> k x

I understand the fundamental uses of continuation monads, but I'm struggling to decipher what's going on in this declaration?

Upvotes: 1

Views: 159

Answers (1)

K. A. Buhr
K. A. Buhr

Reputation: 50864

It might help to see that a C m a is really just a computation -- over an abstract Action m type -- of an a expressed in continuation passing style (a -> Action m) -> Action m, so the data constructor C and the corresponding record selector apply are just syntactic fluff. Rewriting without them and without an explicit monad instance, you get the following equivalent code. (Note that the type Cnt here is just a continuation, not a continuation monad. The continuation monad in Control.Monad.Trans.Cont is more like my CPS type.)

type Cnt m a = (a -> Action m)   -- a continuation, not a Cont monad
type CPS m a = Cnt m a -> Action m
bind :: CPS m a -> (a -> CPS m b) -> CPS m b
cps_a `bind` a_to_cps_b = \cont_b -> cps_a (\a -> a_to_cps_b a cont_b)

or the slightly more verbose:

cps_a `bind` a_to_cps_b =
  \cont_b -> cps_a (\a -> let cps_b = a_to_cps_b a in cps_b cont_b)

How does this work? Well, the part in parentheses has a free variable cont_b that's a b-continuation; but, given this continuation, it's just an a-continuation that uses a_to_cps_b to construct a b-computation (in CPS style) which is applied to the free cont_b continuation. In a nutshell, the part in parentheses is the supplied a_to_cps_b wrapped up in an a-continuation. To combine it with cps_a, we just apply cps_a to this a-continuation, and that represents the combination of the a-computation represented by cps_a with the map a_to_cps_b that yields a b-computation, all expressed in CPS with a free variable b_cont. Abstracting over this free variable gives us the CPS m b that we need.

I think that might help make the whole thing easier to understand, and you can now go back to the original definition, recognizing that \a -> apply (f a) k is really an a-continuation version of f :: a -> C m b expressed in terms of a free variable k representing a b-continuation. apply m can be used to apply the a-computation m to this a-continuation, and we're left with something that combines the a-computation m with the map f from an a to a b-computation, all expressed in terms of a free b-continuation named k, which we can lambda-abstract to construct the needed b-computation which the bind operator should return.

Upvotes: 4

Related Questions