performance of monads

[Paul Hudak]

Eric Allen Wohlstadter wrote:
> I see a lot of literature that says that monads "simulate" the effects of
> imperative programming concepts. It seems to me that the relative
> performance of monadic implementations must be equivalant to imperative
> ones to provide a strong case for functional programming. For example, in
> the Exception handling monad it seems that the "bind" function must be
> called continously to pass the Error value back to an error handling
> function. However, in imperative languages we can make an immediate
> non-local transfer of control. Similiar is the way State is handled. Do
> compilers for haskell do any sort of optimization on these monadic
> operations or is it all as ineffecient as it looks.

I agree with others who mentioned that viewing monads as simply
providing a way to sequentialize things or to program imperatively is
the wrong way to look at them.  Remember that an equally satisfactory
syntax for the "do" notation is "monad comprehensions", which have less
of a sequential feel.  And there are many instances of monads that have
nothing to do with conventional imperative programming.

That said, the EFFICIENCY of monads is often poorly understood.  To
state the obvious, just because you program something in a monad doesn't
make it efficient.  In particular, a state monad does not guarantee that
the state will actually be updated "in place".  The monad only hides the
state, and creates an OPPORTUNITY for it to be updated in place.  But,
for example, if you add an operation that returns the entire state as a
value, then the "single-threadedness" property is in fact lost, and
in-place update becomes as problematical as it always is.

This is an issue that I and my student (Chih-Ping Chen) studied a few
years ago, culminating in his PhD thesis and the paper:

  Chih-Ping Chen and Paul Hudak, "Rolling Your Own Mutable ADT --
  A Connection between Linear Types and Monads", Proceedings of 24th
  ACM Symposium on Principles of Programming Languages, ACM Press,
  1997, pp. 54-66.

the abstract of which is:

  A methodology is described whereby a linear ADT may be rigorously
  encapsulated within a state monad.  A CPS-like translation from the
  original ADT axioms into monadic ones is also described and proven
  correct, so that reasoning can be accomplished at the monadic level
  without exposing the state.  The ADT axioms are suitably constrained
  by a linear type system to make this translation possible.  This
  constraint also allows the state to be ``updated in place,'' a notion
  made precise via a graph-rewrite operational semantics.

Best regards,

  -Paul Hudak