>>= implementation for Poor Man's Concurrency Monad

Question

Hi I am trying to implement the Poor Man's Concurrency Monad. Here is my code:

import Control.Monad

data Concurrent a = Concurrent ((a -> Action) -> Action)

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

instance Monad Concurrent where
    (Concurrent ma) >>= f = Concurrent (\x -> ma(\y -> "Something return a Action")) 
    return x = Concurrent (\c -> c x)

Here is my analysis: x has the type of b, y has the type of a, f has the type of (a -> ((b ->Action) -> Action)). In order to figure out "Something return a Action", I firstly calculate (f y), which returns a type of ((b ->Action) -> Action). Then, how can use it with x to generate a Action?

Answer 1

The definition you are looking for reads something like

Concurrent h >>= k  =  Concurrent (\f -> h (\x -> runConcurrent (k x) f))

How did we get there? As always, we let the types do the work. :)

Let us first introduce a helper function:

runConcurrent                 :: Concurrent b -> (b -> Action) -> Action
runConcurrent (Concurrent h)  =  h

If you start out with the left-hand side of your definition

Concurrent h >>= k  =  ...

with h :: (a -> Action) -> Action and k :: a -> Concurrent b, then your goal is to replace ... with an expression of type Concurrent b, isn't it?

How can we construct a value of type Concurrent b? One way is to apply our function k, but that won't work, because we don't have a suitable value of type a available as an argument. So, pretty much the only thing we can do is to apply the data constructor Concurrent which is of type ((b -> Action) -> Action) -> Concurrent b.

That gives:

Concurrent h >>= k = Concurrent ...

Now we have to go and find us an expression of type (b -> Action) -> Action to supply as an argument for Concurrent. We know that expressions of function type can always be constructed through lambda-abstraction:

Concurrent h >>= k  =  Concurrent (\f -> ...)

This gives us f :: b -> Action and the obligation to replace ... with an expresion of type Action. Using one of the Action-constructors directly would be cheating of course ;). To guarantee the genericity of (>>=) (more precisely, to make sure that we end up obeying the monad laws), we treat Action as if it's an abstract datatype. Then, the only way to produce an Action-value is to apply the function h:

Concurrent h >>= k  =  Concurrent (\f -> h ...)

Hence, next we need to supply h with an argument of type a -> Action. That is a function type again, so we throw in another lambda:

Concurrent h >>= k  =  Concurrent (\f -> h (\x -> ...))

Hence, we have x :: a and need to construct a body of type Action. What can we do with a value of type a? We can supply it to the function k. This gives us a value of type Concurrent b, which we can then pass to our helper function runConcurrent:

Concurrent h >>= k  =  Concurrent (\f -> h (\x -> runConcurrent (k x) ...))

This gives us a function of type (b -> Action) -> Action and supplying f as an argument does the trick:

Concurrent h >>= k  =  Concurrent (\f -> h (\x -> runConcurrent (k x) f))