In computer science, arrows or bolts are a type class used in computer programming to describe computations in a pure and declarative fashion. First proposed by computer scientist John Hughes as a generalization of monads, arrows provide a referentially transparent way to express relationships between logical steps in a computation. Unlike monads, arrows don't limit steps to having one and only one input. As a result, they have found use in functional reactive programming, tacit programming (point-free style), parsers, and in other uses.

Motivation and history

While arrows were in use before being recognized as a distinct class, it wasn't until 2000 that John Hughes first published research focusing on them. Until then, monads had proven sufficient for most problems requiring the combination of program logic in pure code. However, some useful libraries, such as the Fudgets library for graphical user interfaces and certain efficient parsers, defied rewriting in a monadic form.

Relation to category theory

In category theory, the Kleisli categories of all monads form a proper subset of Hughes arrows. it has since been proven that arrows are even more general: arrows are not merely equivalent, but directly equal to enriched Freyd categories.

Definition

Like all type classes, arrows can be thought of as a set of qualities that can be applied to any data type. In the programming language Haskell, arrows allow functions (represented in Haskell by symbol) to combine in a reified form. However, the actual term "arrow" may also come from the fact that some (but not all) arrows correspond to the morphisms (also known as "arrows" in category theory) of different Kleisli categories. As a relatively new concept, there is no one, standard definition, but all formulations are logically equivalent, feature some required methods, and strictly obey certain mathematical laws.

Functions

The description currently used by the Haskell standard libraries requires only three basic operations:

  • A type constructor that takes functions from any type to another , and lifts those functions into an arrow between the two types.

<syntaxhighlight lang="haskell">

arr : (s -> t) -> A s t

</syntaxhighlight>

  • A piping method that takes an arrow between two types and converts it into an arrow between tuples. The first elements in the tuples represent the portion of the input and output that is altered, while the second elements are a third type describing an unaltered portion that bypasses the computation. This also limits the use of arrows to describe push-based reactive frameworks that stop unnecessary propagation. Similarly, the use of pairs to tuple values together results in a difficult coding style that requires additional combinators to re-group values, and raises fundamental questions about the equivalence of arrows grouped in different ways. These limits remain an open problem, and extensions such as Generalized Arrows explore these problems.

Much of the utility of arrows is subsumed by more general classes like (which requires only pre- and postcomposition with functions), which have application in . An arrow is essentially a strong profunctor that is also a category, although the laws differ slightly.

References

  • Arrows: A General Interface to Computation
  • A New Notation for Arrows, Ross Paterson, in ICFP, Sep 2001
  • Arrow notation ghc manual

<!-- Hidden categories below -->