Monads, Arrows, and Idioms

Philip Wadler

The arrow calculus

Sam Lindley, Philip Wadler, and Jeremy Yalloop, Journal of Functional Programming 20(1):51&em;69, 2010.

We introduce the arrow calculus, a metalanguage for manipulating Hughes’s arrows with close relations both to Moggi’s metalanguage for monads and to Paterson’s arrow notation. Arrows are classically defined by extending lambda calculus with three constructs satisfying nine (somewhat idiosyncratic) laws; in contrast, the arrow calculus adds four constructs satisfying five laws (which fit two well-known patterns). The five laws were previously known to be sound; we show that they are also complete, and hence that the five laws may replace the nine.

Available in: pdf, doi.

Monadic constraint programming

Tom Schrijvers, Peter Stuckey, and Philip Wadler Journal of Functional Programming 19(6):663&em;697, 2009.

A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program. In this paper we give a monadic definition of constraint programming in which the solver is defined as a monad threaded through the monadic search tree. We are then able to define search and search strategies as first-class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible.

Available in: pdf, doi.

Idioms are oblivious, arrows are meticulous, monads are promiscuous

Sam Lindley, Philip Wadler, Jeremy Yallop. MSFP 2008.

We revisit the connection between three notions of computation: Moggi's monads, Hughes's arrows and McBride and Paterson's idioms (also called applicative functors). We show that idioms are equivalent to arrows that satisfy the type isomorphism A ~> B = 1 ~> (A -> B) and that monads are equivalent to arrows that satisfy the type isomorphism A ~> B = A -> (1 ~> B). Further, idioms embed into arrows and arrows embed into monads.

Available in: pdf.

The marriage of effects and monads

Philip Wadler and Peter Thiemann. ACM Transactions on Computational Logic, 4(1):1-32, January 2003.

Gifford and others proposed an effect typing discipline to delimit the scope of computational effects within a program, while Moggi and others proposed monads for much the same purpose. Here we marry effects to monads, uniting two previously separate lines of research. In particular, we show that the type, region, and effect system of Talpin and Jouvelot carries over directly to an analogous system for monads, including a type and effect reconstruction algorithm. The same technique should allow one to transpose any effect systems into a corresponding monad system.

This is the journal version of the ICFP effects paper.

Available in: pdf, dvi, ps, dvi.gz, ps.gz, ACM portal.

The marriage of effects and monads

Philip Wadler. International Conference on Functional Programming, Baltimore, September 1998.

This is the conference version of the ToCL paper.

Available in: dvi, ps, dvi.gz, ps.gz, ACM portal.

How to declare an imperative

Philip Wadler. ACM Computing Surveys, 29(3):240--263, September 1997. A shorter version was an invited paper at ILPS 95, appearing in John Lloyd, editor, International Logic Programming Symposium, MIT Press, December 1995.

This tutorial describes the use of a monad to integrate interaction into a purely declarative language. This technique has been implemented in the higher-order functional language Haskell. A sketch is given of how it might be added to a first-order language for logic programming.

Available in: dvi, ps, dvi.gz, ps.gz, ACM portal.

Monads and composable continuations

Philip Wadler. Lisp and Symbolic Computation, Special issue on continuations, 7(1):39-56, January 1994.

Moggi's use of monads to factor semantics is used to model the composable continuations of Danvy and Filinski. This yields some insights into the type systems proposed by Murthy and by Danvy and Filinski. Interestingly, modelling some aspects of composable continuations requires a structure that is almost, but not quite, a monad.

Available in: dvi, ps, dvi.gz, ps.gz.

Imperative functional programming

Simon Peyton Jones and Philip Wadler. 20'th Symposium on Principles of Programming Languages, ACM Press, Charlotte, North Carolina, January 1993.

We present a new model, based on monads, for performing input/output in a non-strict, purely functional language. It is composable, extensible, efficient, requires no extensions to the type system, and extends smoothly to incorporate mixed-language working and in-place array updates.

Available in: dvi, ps, dvi.gz, ps.gz, ACM portal.

Monads for functional programming

Philip Wadler. In M. Broy, editor, Marktoberdorf Summer School on Program Design Calculi, Springer Verlag, NATO ASI Series F: Computer and systems sciences, Volume 118, August 1992. Also in J. Jeuring and E. Meijer, editors, Advanced Functional Programming, Springer Verlag, LNCS 925, 1995. Some errata fixed August 2001.

The use of monads to structure functional programs is described. Monads provide a convenient framework for simulating effects found in other languages, such as global state, exception handling, output, or non-determinism. Three case studies are looked at in detail: how monads ease the modification of a simple evaluator; how monads act as the basis of a datatype of arrays subject to in-place update; and how monads can be used to build parsers.

Keywords: programming languages / functional programming / category theory / monads / pure vs. impure functional languages / semantics / state / parsers.

Available in: pdf, dvi, ps

Comprehending monads

Philip Wadler. Mathematical Structures in Computer Science, Special issue of selected papers from 6'th Conference on Lisp and Functional Programming, 2:461-493, 1992.

Category theorists invented monads in the 1960's to concisely express certain aspects of universal algebra. Functional programmers invented list comprehensions in the 1970's to concisely express certain programs involving lists. This paper shows how list comprehensions may be generalised to an arbitrary monad, and how the resulting programming feature can concisely express in a pure functional language some programs that manipulate state, handle exceptions, parse text, or invoke continuations. A new solution to the old problem of destructive array update is also presented. No knowledge of category theory is assumed.

Available in: dvi, ps, dvi.gz, ps.gz.

Combining monads

David King and Philip Wadler. Glasgow Workshop on Functional Programming, Springer Verlag Workshops in Computing Series, Ayr, July 1992.

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.

Available in: dvi, ps, dvi.gz, ps.gz.

The essence of functional programming

Philip Wadler. Invited talk, 19'th Symposium on Principles of Programming Languages, ACM Press, Albuquerque, January 1992.

This paper explores the use monads to structure functional programs. No prior knowledge of monads or category theory is required.

Monads increase the ease with which programs may be modified. They can mimic the effect of impure features such as exceptions, state, and continuations; and also provide effects not easily achieved with such features. The types of a program reflect which effects occur.

The first section is an extended example of the use of monads. A simple interpreter is modified to support various extra features: error messages, state, output, and non-deterministic choice. The second section describes the relation between monads and continuation-passing style. The third section sketches how monads are used in a compiler for Haskell that is written in Haskell.

Available in: dvi, ps, dvi.gz, ps.gz, ACM portal.

See also

Philip Wadler,