Sat Jul 16 09:39:01 CEST 2011

Monad intuition

Problem: I'm trying to express a data flow graph-constructing monad,
but I find that simply "dreaming it up" doesn't work.  I'm missing
some key insight.

It's entirely trivial to do the computation in Scheme, using a local
mutable variable, and piggy-backing on the order of evaluation.

I know from afar that it is possible to do it using a
state-continuation monad[1].  This approach seems to be essential.  I
don't feel it.

Maybe it has to do with piggy-backing on the order of evaluation?
Because you can't do that in Haskell, it has to be made explicit
somehow, and the CPS Monad does exactly that.

So let's take that as the running assumption.

  The CPS monad is essential.

Type and implementation of CPS monad's bind:

   bind :: Ma -> f -> Mb

   ((t -> r) ->r)   -> (t -> (t' -> r) -> r)  ->   ((t'-> r) -> r)

   bind = \c f k -> c (\ t -> f t k)

In words this is straightforward.  A composition of a CPS computation
c and a function f that produces a CPS computation is obtained by
running c, passing it a new continuation.  That continuation is
created by running the CPS computation f t with the upstream
continuation k, where t is the result from computation c.

The funny thing here is that it is really straightforward to explain
the definition, but somehow I did not make the click yet to
internalize it.

[1] entry://../meta/20110117-141622