Combining Monads

David J. King Philip Wadler

University of Glasgow?

Abstract

Monads provide a way of structuring functional programs. Most real applications require a combination of primitive monads. Here we describe how some monads may be combined with others to yield a combined monad.

1 Introduction

Monads are taking root in the field of functional programming. Although their origins lay in the abstractions of category theory, they have a wide range of practical applications. Moggi [6] showed how they could be used to structure the semantics of computations. Since then Wadler [9, 10] adapted this idea to structure functional programs. When structuring functional programs like parsers, type checkers or interpreters, it is often the case that the monad needed is a combination of many, a so called combined monad.

For our purposes, we will think of a monad as a type constructor, together with three functions that must satisfy certain laws. For instance, we may have an interpreter and wish it to return, not just a value, but the number of reduction steps taken to reach the value. Later, we may want our interpreter either to return a value or an error message. Without using a monad or a similar discipline, it would be a messy undertaking to do in a purely functional programming language. If however our interpreter was written in a monadic style, we would merely have to change the monad to change what extra information the interpreter should return. An analogy can be drawn with a spreadsheet package which has rows relative to some formula. Instead of changing every element in a row we only have to change the formula to which the row is related.

For our interpreter to return the number of reductions and error messages as well it is appropriate that we use a combined monad with both properties. The construction of a combined monad is not always trivial, so it would be useful to have a systematic way of combining monads. Unfortunately, a method does not exist which combines any monad M with any monad N . However, it is conceivable that we may have a library of useful primitive monads, and for each one a technique for combining it with others. Perhaps our library could be divided into collections of monads which can be combined using the same recipe.

In this paper we will look at the class of monads containing trees, lists, bags and sets and consider how they may be combined with others. Lists will be studied first, and it will be shown that the list monad L can be combined

?Authors' address: Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, Scotland, United Kingdom. Electronic mail: fgnik, [email protected].

To appear in Functional Programming, Glasgow 1992, Ayr, Scotland, J. Launchbury and P.M. Sansom, editors, Springer Verlag, Workshops in Computing, 1993.