Arrow

Parsers/streaming, data pipelines

Published:
functional-programming category-theory arrow arrow-combinators profunctor freyd-category premonoidal-category parser-combinators data-pipelines state-machines circuit-design 
    _    ____  ____   _____        ______
   / \  |  _ \|  _ \ / _ \ \      / / ___|
  / _ \ | |_) | |_) | | | \ \ /\ / /\___ \
 / ___ \|  _ <|  _ <| |_| |\ V  V /  ___) |
/_/   \_\_| \_\_| \_\\___/  \_/\_/  |____/

Back in arrow category we touched upon the Arrow abstraction. Now it is time to dive deeper into this underappreciated idea.

If monads are the celebrities of functional programming — with their own conferences, blog posts, and tutorial wars — then Arrows are the skilled craftspeople working quietly behind the scenes. They give a common interface to computations for which a monadic interface may be unnatural or too restrictive.[8]

Not all computations need the full power of monads, but many need more structure than functors provide.

This creates a sweet spot where Arrows shine:

  1. 🎯 Structured Computation: An explicit input-output interface for effectful or otherwise structured computations
  2. 🔄 Composition: Natural ways to combine and sequence computations
  3. 📊 Static Analysis: Structure that can be analyzed without execution
  4. ⚡ Optimization: Opportunities for program transformation and improvement
  5. 🧩 Domain Modeling: Perfect for circuits, parsers, streams, and state machines

These abstractions emphasize different forms of composition:

Functor       mapping values in a context
Applicative   combining context-independent computations
Arrow         composing input-output computations
Monad         choosing later computations from earlier values

Arrows are useful when you need:

  • More than mapping: Your computations have explicit inputs and outputs
  • Restricted dependency: Later stages do not need to construct arbitrary new stages from intermediate values
  • Visible wiring: The chosen Arrow representation preserves enough structure to analyze, optimize, or visualize the computation

Monads support value-dependent composition: a result can determine which computation is constructed next. Basic Arrow notation instead fixes the computational stages and their wiring statically. Whether an Arrow value itself can be inspected depends on its concrete representation.

This difference unlocks several options:

  • Introspection: A reified Arrow representation can be examined without being executed
  • Optimization: A domain-specific Arrow can support transformations before interpretation
  • Visualization: A reified computation graph can produce diagrams or analysis reports
  • Testing: Arrow laws and domain-specific structure can be tested independently

Consider these real-world scenarios where Arrows excel:

  • Circuit Design: Electrical or logical circuits with clear input/output flows
  • Data Processing Pipelines: ETL operations with known transformation stages
  • Protocol Parsers: Network protocols with structured parsing requirements
  • Signal Processing: Audio/video processing with filter chains
  • Configuration Systems: Complex configurations with validation and transformation

It is time to restrain our monadic powers a little and learn some computational discipline.

Arrow #

At its heart, an Arrow generalizes functions while retaining identity and composition. Where functions compose with (.), Arrow computations form a Category and gain combinators for routing product-shaped inputs.[7]

Arrows capture the essence of "structured computation" — computations that have a clear input-output relationship but may involve complex internal transformations, effects, or computational context. They are not literally an intermediate point in a single hierarchy between functions and monads; they provide a different interface to composition.

In addition to pure transformations, Arrow instances can represent computations involving state or failure. Extra capabilities such as branching and feedback are expressed by subclasses including ArrowChoice and ArrowLoop.

Formal Definition #

In Haskell, an Arrow is a binary type constructor whose minimal operations are arr and either first or (***), together with the identity and composition supplied by Category. The remaining combinators have default definitions.[6]

class Category arr => Arrow arr where
  arr    :: (b -> c) -> arr b c
  first  :: arr b c -> arr (b, d) (c, d)
  second :: arr b c -> arr (d, b) (d, c)
  (***)  :: arr b c -> arr b' c' -> arr (b, b') (c, c')
  (&&&)  :: arr b c -> arr b c' -> arr b (c, c')

The Category constraint requires:

class Category arr where
  id  :: arr a a                         -- Identity arrow
  (.) :: arr b c -> arr a b -> arr a c   -- Arrow composition

Arrow laws:[10]

  1. Identity preservation: arr id = id
  2. Composition preservation: arr (f >>> g) = arr f >>> arr g
  3. Pure-product compatibility: first (arr f) = arr (first f)
  4. Composition under first: first (f >>> g) = first f >>> first g
  5. Projection coherence: first f >>> arr fst = arr fst >>> f
  6. Naturality in the untouched component: first f >>> arr (id *** g) = arr (id *** g) >>> first f
  7. Associativity coherence: first (first f) >>> arr assoc = arr assoc >>> first f

Here assoc ((a, b), c) = (a, (b, c)). In laws 3 and 6, the operations inside arr are the corresponding operations on ordinary functions.

These laws ensure that Arrow operations interact coherently with pure functions, composition, and products.

The Arrow methods work as follows:

  • arr: Lifts any pure function into the Arrow context
  • first: Takes an Arrow and makes it operate on the first component of a pair, leaving the second component unchanged
  • second: Similarly operates on the second component of a pair
  • (***): Routes the two components of a pair through two Arrows and pairs their outputs
  • (&&&): Sends one input through two Arrows and pairs their outputs
  • id: The do-nothing Arrow that passes input through unchanged
  • (.): Composes Arrows sequentially, like function composition but preserving Arrow structure

These operations are sufficient to build complex computational networks. Static analyzability is not guaranteed by the Arrow class alone; it is a property of representations that retain the network as data.

Categorically, an Arrow can be described as an internally strong monoid in a category of profunctors.

Product category #

A product category is a fundamental construction in category theory that allows us to combine two categories into a single, larger category. Understanding product categories is crucial for grasping how Arrows work categorically.[1]

Given two categories C and D, their product category C × D has:

  • Objects: Pairs (A, B) where A is an object in C and B is an object in D
  • Morphisms: Pairs (f, g) : (A, B) → (A', B') where f : A → A' in C and g : B → B' in D
  • Composition: (f', g') ∘ (f, g) = (f' ∘ f, g' ∘ g)
  • Identity: id_{(A,B)} = (id_A, id_B)

Product categories satisfy a universal property: for any category E and functors F : E → C and G : E → D, there exists a unique functor ⟨F, G⟩ : E → C × D such that:

π₁ ∘ ⟨F, G⟩ = F

π₂ ∘ ⟨F, G⟩ = G

This universality makes C × D the categorical product of C and D. For Arrows, the relevant construction is C^op × C: its objects are input-output pairs.

Connection to Haskell types:

For the category of Haskell types and functions:

  • Objects of Hask^op × Hask: Pairs of types (A, B)
  • Morphisms: Pairs of functions, with the first component reversed by Hask^op
  • Arrow computations: arr A B is the collection, represented by a Haskell type, assigned to the input-output pair (A, B)

The product-category domain accounts for the contravariant input and covariant output of arr A B. The Arrow operations require additional structure beyond the product category itself.

Categorical Arrow #

Let C be a category of pure computations with finite products. The carrier of an Arrow is a profunctor:

A : C^op × C → Set

Here:

  • C^op × C is the product of the opposite category and the original category
  • C^op has the same objects as C but all arrows reversed
  • A(X, Y) is the set of Arrow computations from X to Y

The pair (X, Y) has:

  • X in the contravariant input position
  • Y in the covariant output position

The profunctor is only the carrier. An Arrow also has:[9]

  1. A unit that embeds pure morphisms, corresponding to arr
  2. An associative multiplication, corresponding to Arrow composition
  3. An internal strength, corresponding to carrying an untouched value alongside a computation with first
  4. The Arrow laws, which make these operations coherent

Equivalently, an Arrow is an internally strong monoid in the monoidal category of profunctors on C, where the tensor is profunctor composition. This is the precise sense in which Arrows, like monads, are monoids.

Profunctorial structure:

The type constructor arr b c is contravariant in its first argument and covariant in its second:

  • Contravariant in the first argument (input type)
  • Covariant in the second argument (output type)

These mappings can be derived by composing with lifted pure functions:

lmap f p = arr f >>> p
rmap g p = p >>> arr g

Monoidal Structure #

We are going to need to brush up on our monoidal category knowledge.

A monoidal category (C, ⊗, I) consists of:[3]

  • A category C
  • A bifunctor ⊗ : C × C → C (the monoidal product)
  • An object I (the unit object)
  • Natural isomorphisms for associativity, left unit, and right unit

Ignoring Haskell's nontermination and other semantic complications, the usual model treats Hask as cartesian monoidal:

  • Category: Hask (types and functions)
  • Product: (×) (tuple formation)
  • Unit: () (unit type)

An Arrow determines a category of computations with:

  • Objects: The objects of the underlying pure category
  • Morphisms: Elements of A(X, Y), represented in Haskell by values of type arr x y
  • Identity: arr id
  • Composition: (>>>)

In general, this computation category is premonoidal, not monoidal: the order of effects may matter. The operations first and second tensor an effectful computation with an identity computation on either side:

first  : arr(A,B) → arr(A×C, B×C)
second : arr(A,B) → arr(C×A, C×B)

Together with the identity-on-objects functor that embeds pure computations via arr, this forms a Freyd category. The internal strength in the profunctor formulation and the premonoidal structure in the Freyd-category formulation express the same Arrow structure.

Freyd Category #

Before defining a Freyd category, we need two supporting ideas.

A premonoidal category resembles a monoidal category, but its tensor need only be functorial in each argument separately. Given computations f : X → X' and g : Y → Y', applying f and then g need not equal applying g and then f. This distinction models the observable order of effects.

A morphism f : X → X' is central when it commutes with every morphism g : Y → Y' acting on another component. In particular, the following two execution orders must agree:

(f ⊗ id_Y) >>> (id_X' ⊗ g) = (id_X ⊗ g) >>> (f ⊗ id_Y')

The analogous equation must also hold with f acting on the right component. Pure computations are central because moving them across an independent effect does not change the effect's observable order.

Strictly, a Freyd category consists of:[11]

  1. A category C with finite products, representing values and pure computations
  2. A symmetric premonoidal category D, representing possibly effectful computations
  3. An identity-on-objects functor J : C → D that strictly preserves the premonoidal structure and maps every morphism of C to a central morphism of D

Because J is identity-on-objects, C and D have the same objects but may have different morphisms. Strict preservation means, in particular, that:

  • J(X × Y) = X ⊗ Y
  • J(1) = I, where 1 and I are the respective unit objects
  • J preserves the associators, unitors, and symmetry on the nose

An Arrow A over C produces such a Freyd category:

  • The objects of D are the objects of C
  • D(X, Y) = A(X, Y)
  • The identity in D is arr id
  • Composition in D is (>>>)
  • J acts on morphisms as J(f) = arr f
  • Tensoring an Arrow with an identity is given by first or second

The Arrow laws ensure that these definitions are coherent and that lifted pure morphisms are central. Conversely, under the standard size assumptions, a Freyd category determines an Arrow.

Lax Monoidal Functors #

A lax monoidal functor between monoidal categories (C, ⊗, I) and (D, ⊛, J) consists of:[2][4]

  • A functor F : C → D
  • A morphism φ₀ : J → F(I)
  • A natural family φ₂ : F(A) ⊛ F(B) → F(A ⊗ B)
  • Coherence laws relating these maps to associativity and the unitors

The word "lax" means that φ₀ and φ₂ need not be isomorphisms. It does not imply that values or components are necessarily lost.

Applicative functors as lax monoidal functors. We have seen this correspondence as well.

Applicative functors correspond to lax monoidal endofunctors on Hask with its cartesian monoidal structure:

class Functor f => Applicative f where
  pure  :: a -> f a                    -- pure () represents φ₀: () → f ()
  (<*>) :: f (a -> b) -> f a -> f b    -- Derived from φ₂

The lax monoidal structure is:

-- φ₀: Unit preservation
pure :: () -> f ()

-- φ₂: Lax product preservation
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
-- Equivalently: f a × f b → f (a × b)

The map combines two independent effects into one product-shaped effect. The Applicative interface does not allow the result of the first effect to choose the second effect.

Strong Monoidal Functors #

A strong monoidal functor is a lax monoidal functor for which the structure maps are isomorphisms:[5]

  • φ₀ : J → F(I) is an isomorphism
  • φ₂ : F(A) ⊛ F(B) → F(A ⊗ B) is a natural isomorphism

Their inverses provide maps in the other direction, such as:

F(A ⊗ B) → F(A) ⊛ F(B)

Despite the similar terminology, a Haskell Arrow is not, in general, a strong monoidal functor. Its "internal strength" is a different categorical notion. In particular, (***) does not imply parallel execution: its usual definition sequences first f and second g, and effects need not commute.

The Hierarchy #

Applicatives, Arrows, and monads are related, but they do not form a simple linear hierarchy:

Applicative:  combines independent contextual computations
Monad:        supports value-dependent sequencing
Arrow:        composes computations with explicit input and output
  • Every monad m induces a Kleisli Arrow Kleisli m a b = a → m b
  • Some useful Arrows do not arise naturally from a monadic interface
  • Applicative and Arrow constrain dependency in different ways and operate on type constructors of different arities

It is therefore reasonable to describe Arrows as more structurally constrained than monadic code, but not as strong monoidal functors sitting between Applicative and Monad.

Arrows are internally strong monoids in a suitable category of profunctors; equivalently, they correspond to Freyd categories under standard assumptions.

Operationally, the basic interface provides:

  1. Lifting pure functions (arr)
  2. Operating on products (first/second)
  3. Preserving categorical structure (composition, identity)

These capabilities make Arrows useful for structured computations with explicit data flow. Whether a particular Arrow supports inspection, optimization, parallelism, choice, or feedback depends on its representation and subclasses.

Arrow Subclasses #

The basic Arrow class provides composition and product-shaped routing. Additional type classes introduce capabilities that not every Arrow can support coherently.

ArrowChoice #

ArrowChoice adds branching over sum types, represented in Haskell by Either:

class Arrow arr => ArrowChoice arr where
  left  :: arr b c -> arr (Either b d) (Either c d)
  right :: arr b c -> arr (Either d b) (Either d c)
  (+++) :: arr b c -> arr b' c' -> arr (Either b b') (Either c c')
  (|||) :: arr b d -> arr c d -> arr (Either b c) d

The operations have the following roles:

  • left f applies f to a Left value and passes a Right value through unchanged
  • right f is the mirror image of left f
  • f +++ g routes Left values through f and Right values through g
  • f ||| g handles both alternatives and merges their outputs into one type

The branch is selected by the input's Either tag. The Arrow network still specifies both branches in advance; it does not construct a new Arrow from an intermediate result.

ArrowLoop #

ArrowLoop adds feedback:

class Arrow arr => ArrowLoop arr where
  loop :: arr (b, d) (c, d) -> arr b c

The wrapped Arrow receives an ordinary input b and a feedback input d, then produces an ordinary output c and a new feedback value d. loop ties the feedback output to the feedback input:

        ┌───────────────┐
   b ──>│               │──> c
        │       f       │
        │           d ──┼─┐
        │           ^   │ │
        └───────────│───┘ │
                    └─────┘

This is a fixed-point or feedback construction, not necessarily repeated execution. It is useful for circuits, signal functions, and recursive data flow. Not every Arrow admits a lawful loop; the instance must give a meaningful interpretation to the feedback path.

ArrowApply #

ArrowApply allows an Arrow value itself to arrive as input and then be applied dynamically:

class Arrow arr => ArrowApply arr where
  app :: arr (arr b c, b) c

The input to app is a pair containing an Arrow arr b c and a value b. The supplied Arrow is chosen at runtime and applied to that value to produce c.

This capability crosses the boundary established by basic Arrow notation. The computation graph no longer needs to be fixed in advance because an intermediate value can determine which Arrow runs next. In this precise sense, ArrowApply has the expressive power of monadic computation: every monad produces a Kleisli Arrow with application, and an ArrowApply instance produces a monad through the ArrowMonad construction.

Use ArrowApply when dynamic application is essential. If it appears throughout a design, a direct monadic formulation may be simpler and may communicate the dependency structure more clearly.

Examples #

Circuit Processing with Arrows #

One of the most intuitive applications of Arrows is modeling computational circuits where data flows through interconnected processing units.

While TypeScript doesn't have native Arrow support, we can implement similar patterns using function composition and higher-order functions:

C# can implement Arrow-like patterns using interfaces, generics, and extension methods to create composable circuit processing:

Parser Combinators with Arrows #

Arrows can build parsers with clear structure. This simplified example represents failure with Maybe; richer parser Arrows can retain error details:

C# can implement Arrow-like parser combinators using nullable types, generics, and LINQ-style syntax for structured parsing:

State Machine with Arrows #

Arrows naturally model state machines with clear state transitions:

C# can model Arrow-like state machines using generic classes and composition.

Visualizing Arrow #

1. Basic Arrow Structure

Input ---> [Arrow f] ---> Output
  A                        B

An Arrow `f` transforms input of type `A` to output of type `B`.

2. Arrow Composition (`>>>`)

A ---> [f] ---> B ---> [g] ---> C

Equivalent to:
A ---> [f >>> g] ---> C

Sequential composition: the output of `f` becomes the input of `g`.

3. Product Operations

  3.a First (`first f`)

     ┌─── A ---> [f] ---> B ───┐
     │                         │
(A,C)┤                         ├─(B,C)
     │                         │
     └─── C ──────────── C ────┘

The Arrow `f` operates on the first component, leaving the second unchanged.

  3.b Second (`second g`)

     ┌─── A ─────────────── A ───┐
     │                           │
(A,C)┤                           ├─(A,D)
     │                           │
     └─── C --> [g] --> D ───────┘

The Arrow `g` operates on the second component, leaving the first unchanged.

4. Paired Composition (`f *** g`)

     ┌─── A ---> [f] ---> B ───┐
     │                         │
(A,C)┤                         ├─(B,D)
     │                         │
     └─── C ---> [g] ---> D ───┘


Each Arrow operates on its respective component. The combinator expresses paired routing, not necessarily simultaneous or parallel execution; effects may be sequenced.

5. Arrow Laws Visualization

  5.a Identity Law

A ---> [id] ---> A     (Identity does nothing)

A ---> [f >>> id] ---> B  ≡  A ---> [f] ---> B

  5.b Associativity Law

A ---> [f] ---> B ---> [g] ---> C ---> [h] ---> D

Both groupings are equivalent:
A ---> [(f >>> g) >>> h] ---> D
A ---> [f >>> (g >>> h)] ---> D


6. First/Second Laws

first id ≡ id:

     ┌─── A ─────── A ───┐              ┌─── A ─────── A ───┐
     │                   │              │                   │
(A,C)┤                   ├─(A,C) ≡ (A,C)┤                   ├─(A,C)
     │                   │              │                   │
     └─── C ─────── C ───┘              └─── C ─────── C ───┘
            first id                              id

first (f >>> g) ≡ first f >>> first g:

     ┌─── A ---> [f] ---> B ---> [g] ---> C ───┐
     │                                         │
(A,D)┤                                         ├─(C,D)
     │                                         │
     └─────── D ────────────────── D ──────────┘
                 first (f >>> g)

         ≡

     ┌─── A ---> [f] ---> B ───┐      ┌─── B ---> [g] ---> C ───┐
     │                         │      │                         │
(A,D)┤                         ├─(B,D)┤                         ├─(C,D)
     │                         │      │                         │
     └───── D ────────── D ────┘      └───── D ────────── D ────┘
                first f                          first g

7. Complex Arrow Network

                    ┌─── [f₁] ---> B₁ ───┐
                    │                    │
         ┌─── A₁ ───┤                    │---> [combine] ---> D
         │          │                    │
Input ───┤          └─── [f₂] ---> B₂ ───┘
         │
         └─── A₂ ------> [g] ----------------> C---> [final] ---> Output

Multi-path Arrow computation with fan-out and fan-in

8. Profunctor View

Pure input map                         Pure output map
X' -------- u --------> X             Y -------- v --------> Y'
                       │              │
                       └── p : A(X,Y) ┘

              arr u >>> p >>> arr v
                       │
                       ▼
                    A(X',Y')

The input position is contravariant; the output position is covariant:

                  A : Cᵒᵖ × C ---> Set
                      (X,Y) |---> A(X,Y)

9. Freyd Category: Pure and Effectful Computations

             pure category C
          X -------- f --------> Y
          │                      │
          │ same objects         │ same objects
          ▼                      ▼
          X ====== arr f ======> Y
          X ======== p =========> Y
          computation category D

                    J : C ---> D
                    J(f) = arr f

`C` contains pure morphisms. `D` also contains general Arrow
computations such as `p`. The functor `J` embeds the pure ones.

10. Premonoidal Ordering

For p : A -> B and q : C -> D, two orders are possible:

  (A,C) -- first p --> (B,C) -- second q --> (B,D)

  (A,C) -- second q -> (A,D) -- first p  --> (B,D)

In general:

        first p >>> second q  ≠  second q >>> first p

The tensor is therefore premonoidal: each side is functorial on its
own, but independent effectful computations need not commute.

11. Central Pure Morphisms

When h is pure, `arr h` is central, so it commutes with an independent
effect q:

 first (arr h) >>> second q  =  second q >>> first (arr h)

 (A,C) -- first (arr h) --> (B,C) -- second q ------> (B,D)
   ║                                                        ║
   ╚══ second q =========> (A,D) == first (arr h) =========╝

The upper path applies the pure map first; the lower path applies the
independent effect first. Centrality says that the results agree.

12. Two Equivalent Categorical Views

  Monoid in internally strong profunctors    Freyd category

       A : Cᵒᵖ × C -> Set                  J : C -> D
       arr      = unit                     pure embedding
       (>>>)    = multiplication           composition in D
       first    = internal strength         premonoidal structure

                         equivalent
              under the standard assumptions

Conclusion #

Arrows offer an insight into the nature of computation: not every problem needs value-dependent monadic sequencing, while many problems need more structure than plain function composition provides. Arrows trade some forms of dynamic composition for an explicit input-output interface.

What makes basic Arrows useful is not a capability unavailable to monads, but the structure exposed by restricting value-dependent composition.

🔍 Static structure: Some Arrow representations retain an analyzable shape before execution

  • Reified circuits can be rendered as diagrams
  • Reified parser structure can support analysis or optimization
  • Domain-specific representations can track resource requirements

⚡ Optimization opportunities: A suitable representation can enable transformations

  • Independent circuit stages may be candidates for parallel execution
  • Parser descriptions may be transformed into efficient state machines
  • Explicit resource information may support ahead-of-time optimization

🧩 Compositional clarity: The Arrow laws ensure coherent behavior

  • f >>> (g >>> h) = (f >>> g) >>> h — composition is associative
  • first f >>> first g = first (f >>> g) — structure is preserved
  • arr id = id — pure functions lift cleanly

Arrows shine in domains where:

  • Structure Matters: When the shape of computation is as important as the result
  • Static Analysis: When you need to examine computations without running them
  • Resource Management: When computational resources need careful coordination
  • Domain Modeling: When your problem naturally fits Arrow patterns

Avoid Arrows when you need:

  • Dynamic selection of computations from intermediate results (use a monad)
  • Simple independent contextual computations (use Applicative)
  • Pure transformations without computational context (use ordinary functions or Functor as appropriate)

As functional programming matures, Arrows represent an important lesson: constraint enables capability. By voluntarily limiting our computational power, we gain new abilities.

The Arrow way: Embrace structure, gain insight, and discover that sometimes the most powerful abstraction is the one that knows its limits.

Source code #

Reference implementation

References

  1. Product (category theory) ·
  2. Monoidal functor ·
  3. Monoidal Categories ·
  4. Lax Monoidal Functors ·
  5. Strong Monoidal Functors ·
  6. Arrow tutorial ·
  7. Arrow ·
  8. Programming with arrows ·
  9. Arrows, like Monads, are Monoids ·
  10. Control.Arrow ·
  11. Categorical Semantics for Arrows ·

Continue exploring