Arrows: A General Interface to Computation

Papers relating to arrows, divided into generalities, applications and related theoretical work. The list is also available in bibtex format.

Arrows in general

John Hughes, Generalising Monads to Arrows, in Science of Computer Programming 37, pp67-111, May 2000.

The paper introducing "arrows" -- a friendly and comprehensive introduction. (It doesn't even assume a prior knowledge of monads.)

An old draft is available online [ps, pdf]. The main differences in the final version are:

  • the +++ and <+> operators are swapped,
  • the onto and one-to-one laws are discarded in favour of an identity law,
  • associativity laws have been added, and
  • the last few sections use a variant of the arrow notation of [Pat01].
Ross Paterson, A New Notation for Arrows, in ICFP 2001, Firenze, Italy, pp229-240.

Introduces the arrow notation, but will make more sense if you read one of the other papers first.

Ross Paterson, Arrows and Computation, in The Fun of Programming (Jeremy Gibbons and Oege de Moor, Eds.), pp201-222, Palgrave, 2003.

An overview of arrows from first principles, with a simplified account of a subset of the arrow notation.

John Hughes, Programming with Arrows, in 5th International Summer School on Advanced Functional Programming, LNCS 3622, pp 73-129, Springer, 2005. [pdf].

A tutorial introduction to arrows and arrow notation.

Applications of arrows

Anthony Courtney and Conal Elliott, Genuinely Functional User Interfaces, in Haskell Workshop 2001, Firenze, Italy, pp41-69.

A GUI toolkit descended from Fran and FRP, but based on an arrow type, and using the arrow notation of [Pat01].

Paul Hudak, Henrik Nilsson, Anthony Courtney and Jon Peterson, Arrows, Robots, and Functional Reactive Programming, in Advanced Functional Programming, 4th International School, (Johan Jeuring and Simon Peyton Jones eds.), Oxford, Springer LNCS 2638, 2003.

A tutorial introduction to Yampa, the latest incarnation of FRP.

Patrik Jansson and Johan Jeuring, Polytypic compact printing and parsing, in Proceedings European Symposium on Programming, LNCS 1576, pp273-287, Springer, 1999.

This paper uses state transformers, which could have been cast as monads, but the arrow formulation greatly simplifies the calculations.

Patrik Jansson and Johan Jeuring, Polytypic data conversion programs, Science of Computer Programming 43(1), pp35-75, 2002.

An extension of the previous paper, additionally using static arrows.

Sava Krstic, John Launchbury and Dusko Pavlovic, Hyperfunctions, Workshop on Fixed Points in Computer Science, Sep 2001. [ps, pdf]

A novel example of an arrow type.

Hai Liu, Eric Cheng, and Paul Hudak. Causal Commutative Arrows and Their Optimization. Proceedings of the 14th ACM SIGPLAN International Conference on Functional Programming (ICFP 2009). Edinburgh, Scotland. August 2009.

Henrik Nilsson, Anthony Courtney and Jon Peterson, Functional Reactive Programming, Continued, in Haskell Workshop 2002, Pittsburgh, pp51-64.

Decribes the arrowized version of FRP.

Related theoretical work

Here is an incomplete list of theoretical papers dealing with structures similar to arrows.

Richard Blute, J.R.B. Cockett and R.A.G. Seely. Categories for Computation in Context and Unified Logic, in Journal of Pure and Applied Algebra 116:49-98, 1997. [dvi.gz, ps.gz]

This paper defines a number of structures, intended for the semantics of linear logics. Arrows may be seen as strict versions of these. Where the arrow functors arr and lift preserve objects, Blute et al introduce mediating morphisms, with dozens of coherence conditions. They also deal with cocontext, which subsumes ArrowChoice in the same way.

John Power and Edmund Robinson. Premonoidal Categories and Notions of Computation, in Mathematical Structures in Computer Science 7(5):453-468, 1997. [dvi.gz, dvi, ps.gz, ps]

This paper introduces premonoidal categories and functors as generalizations of monoidal ones. They then propose a general model of computation: a strict symmetric premonoidal functor j: C -> K, where C is symmetric monoidal. The Kleisli construction on a strong monad is a special case.

If the monoidal structure on C is given by products, this definition is equivalent to arrows. In [PT99] this case is called a Freyd-category.

Implicit in Power and Robinson's definition is a notion of morphism between these structures, which is stronger (and less satisfactory) than that used by Hughes.

John Power and Hayo Thielecke. Environments, Continuation Semantics and Indexed Categories, in Proc. Theoretical Aspects of Computer Science, LNCS 1281, pp 391-414, Springer, 1997. [ps]

Freyd-categories are shown to be equivalent to a class of indexed categories called kappa-categories.

John Power and Hayo Thielecke. Closed Freyd- and kappa-categories, ICALP'99, LNCS 1644, pp 625-634, Springer, 1999. [ps]

Deals with the case where arr.first has a right adjoint (ArrowApply), and so is equivalent to the Kleisli category of a monad. This leads to an straightforward semantics for Moggi's computational lambda-calculus. The first mention of the term Freyd-category.

Ross Paterson