More on monads

[Ralph Becket]

I've been looking more closely at monads and, upon reflection, they
seem to be amazingly useful constructions (I say this with a complete
lack of experience, but the FP community swears by them - to every
problem the answer is "monads!" there).

If I've got this right, a monad is basically a type which wraps up a
value of some computation with some `state'.  There are two basic
operations: constructing a monad from an initial value and applying a
monad to a computation producing a monad.  The identity monad is then
something like

:- type monad(T) == T.

:- func unit(T) = monad(T).
unit(A) = A.

:- func bind(monad(T), func(T) = monad(U)) = monad(U).
bind(A, K) = K(A).

So code to use this would go something like this:

:- func f(T) = monad(U).		% For some T and U.

f(A) =
	bind( unit(A),			func(X) =
	bind( expr1,			func(Y) =
	bind( expr2,			func(Z) =
	      expr3)))

where normally the unit/1 would be unnecessary except at the
top-level: one would be passing monads around.  So far, this just
appears to be adding syntax to no effect (as one would expect with the
identity monad).  However, by simply changing the definition of unit/1
and bind/2 and the monad/1 type, all sorts of clever tricks can be
arranged.  Basically, altering the bind/2 operation to be sensitive to
the contents of the monad lets you put in various checking code at
each step in the computation.  This gives you a direct and minimal way
of adding new functionality to code.

I refer the reader to ``The Essence of Functional Programming'' by
Philip Wadler for a straightforward and impressive demo of how natty
these things are (you can fetch the paper from
http://www.di.uminho.pt/ftp/pub/DI/Fundamentos/Papers/mirror-ImperialCollege/WadlerP

BUT, the point of this note re: Mercury is that, while I believe the
compiler can unpack all the higher order stuff and simplify 90% of all
the unused machinery away from the computation, it seems to me that
there is a lot of unpacking of dead monad objects only to be followed
by direct repackaging with a new `value' - this isn't going to be
terribly efficient without compile-time garbage collection.  Am I
right about this?

Ralph

-- 
Ralph Becket  |  rwab1 at cam.sri.com  |  http://www.cam.sri.com/people/becket.html