Composing Monads

Composing Monads

Mark P. Jones and Luc Duponcheel, Research Report YALEU/DCS/RR-1004, Yale University, New Haven, Connecticut, USA, December 1993.


Abstract:

Monads are becoming an increasingly important tool for functional programming. Different monads can be used to model a wide range of programming language features. However, real programs typically require a combination of different features, so it is important to have techniques for combining several features in a single monad. In practice, it is usually possible to construct a monad that supports some specific combination of features. However, the techniques used are typically ad-hoc and it is very difficult to find general techniques for combining arbitrary monads.

This report gives three general constructions for the composition of monads, each of which depends on the existence of an auxiliary function linking the monad structures of the components. In each case, we establish a set of laws that the auxiliary function must satisfy to ensure that the composition is itself a monad.

Using the notation of constructor classes, we describe some specific applications of these constructions. These results are used in the development of a simple expression evaluator that combines exceptions, output and an environment of variable bindings using a composition of three corresponding monads.

(Supported in part by a grant from ARPA, contract number N00014-91-J-4043.)


Available by http in pdf, PostScript, or gzipped dvi. Gofer source is also available.