Sat Jul 16 10:20:01 CEST 2011

Continuation monad : two return types?

The central type in the CPS monad is

    data CPS r t = CPS {runCPS :: (t -> r) -> r}

or without wrapping

    (t -> r) -> r

where k = t -> r is the type of the continuation function.  t is the
type of the value that is "returned" from a CPS computation,
i.e. passed from one CPS computation to the next, and r is the overall
result type of the computation.

Why are there 2 return types?  The mind set where this question comes
from has confused me for a long time.  The answer is the following:

  t is the result type of a CPS computation, which is passed to a
  continuation function (t -> r).  This t is the Monad parameter.

  r is the result type of a Haskell expression that is written in CPS
  and does not take part in monadic computation.

The key for me was to understand that r doesn't really matter: i.e. it
does not take part in the bind method.  It is an "impedance match"
between the CPS abstraction - where the result of every computation is
passed to an explicit continuation function - and the Haskell language
in which it is embedded where every function needs to have a return

Stretching the analogy a bit, a CPS function never returns, so its
return type can just as well not exist.  The r type is only necessary
at the boundary of a CPS computation and other Haskell code.