Arrows and Computation

Ross Paterson. The Fun of Programming, edited by Jeremy Gibbons and Oege de Moor, Palgrave, 2003, 201-222.


Many programs and libraries involve components that are `function-like', in that they take inputs and produce outputs, but are not simple functions from inputs to outputs. This chapter explores the features of such `notions of computation', defining a common interface, called `arrows'. This allows all these notions of computation to share infrastructure, such as libraries, proofs or language support. Arrows also provide a useful discipline for structuring many programs, and allow one to program at a greater level of generality. Monads, discussed in Chapter 11 of IFPH, serve a similar purpose, but arrows are more general. In particular, they include notions of computation with static components, independent of the input, as well as computations that consume multiple inputs. We also consider some useful subclasses of arrows, one of which turns out to be equivalent to monads. The others bring choice and feedback to the arrow world.

With this machinery, we can give a common structure to programs based on different notions of computation. The generality of arrows tends to force one into a point-free style, which is useful for proving general properties. However it is not to everyone's taste, and can be awkward for programming specific instances. The solution is a point-wise notation for arrows, which is automatically translated to the functional language Haskell. Each notion of computation thus defines a special sublanguage of Haskell.


gzipped PostScript, gzipped DVI, BibTeX, slides (PDF).