Arrow category

Meta-programming, code as data

Publish at:
arrow-category morphism commutative-diagram functor-category 
    _    ____  ____   _____        __
   / \  |  _ \|  _ \ / _ \ \      / /
  / _ \ | |_) | |_) | | | \ \ /\ / /
 / ___ \|  _ <|  _ <| |_| |\ V  V /
/_/___\_\_| \_\_|_\_\\___/__\_/\_/  ____  ___ _____ ____
 / ___|  / \|_   _| ____/ ___|/ _ \|  _ \|_ _| ____/ ___|
| |     / _ \ | | |  _|| |  _| | | | |_) || ||  _| \___ \
| |___ / ___ \| | | |__| |_| | |_| |  _ < | || |___ ___) |
 \____/_/   \_\_| |_____\____|\___/|_| \_\___|_____|____/

Introduction #

It might be a bit mind-bending, but functions themselves form a category. It has several names: arrow category[1], category of morphisms (and it can be described as the functor category C^[1][2]). From a categorical point of view, for something to be a category, it needs objects, morphisms and some additional properties. If we take an arbitrary category and inspect its morphisms, we can infer that a new category can be constructed, where

  • Objects are morphisms (arrows) in the original category.
  • Morphisms between two arrows f:A -> B and g:C -> D are pairs of morphisms s:A -> C, t:B -> D such that the following square applies transformations in a commutative manner[3]:
A ---f---> B
|          |
s          t
|          |
▼          ▼
C ---g---->D

OK, objects are clear, morphisms - not so much. And what is this commutative thing again? Proving that this category is in fact a category is not that difficult. As an exercise, it illustrates functional thinking at its core. Enough time wasted.

We start with the initial category C, proving that arrow category Arr(C) is category.

For Arr(C) we have:

  • Objects are morphisms (arrows) f:A -> B in C
  • Morphisms are pairs of morphisms (s: A -> C, t: B -> D) in C so, the application of the arrows is commutative (gives the same result whatever the order of the quantities involved). That means, given the square
A ---f---> B
|          |
s          t
|          |
▼          ▼
C ---g---->D

For any morphism (s, t): f -> g in Arr(C), t ∘ f = g ∘ s.

Composition in arrow category #

Visual proof first. If we take two morphisms from the original category, say f and g.

A ---f---> B

C ---g---> D

What we need is a glue that transforms one into another. And that glue is two arrows that connect objects from the top to the objects from the bottom, respectively.

A    B
|    |
s    t
|    |
▼    ▼
C    D

But not in any arbitrary way. Application of g and s consecutively has to be the same as the application of the t and f.

  • g ∘ s = t ∘ f
  • g(s(x)) == t(f(x))

So, the application of the arrows is commutative, and the whole square is called a commutative square.

The final morphism α:f -> g is the one we are interested. Technically it's a morphism (s, t): f -> g that commutes.

  A --f-->B
  |       |
  g       h
  |       |
  ▼       ▼
  A'--f'->B'

Here f: A -> B and f': A' -> B' are objects in our new category, and g: A -> A' and h: B -> B' are morphisms in the original category.

And we can also compose these new types of morphisms. If we put two of them side by side:

  A --f--> B --g-->C
  |        |       |
  k        l       m
  |        |       |
  ▼        ▼       ▼
  A'--f'-->B'--g'->C'

We can get to C' via two ways. From A to A' to B' to C', and from A to B to C to C'. More formally: g'(f'(k(x))) == m(g(f(x))), or g' ∘ f' ∘ k == m ∘ g ∘ f.

The composition is also associative because all the morphisms from original category are associative.

Another way of proving composition is just by following the path of morphisms.

Suppose we have three objects (arrows) in C:

  • f: A -> B
  • g: C -> D
  • h: E -> F

Suppose we have morphisms:

  • (s, t): f -> g where s: A -> C, t: B -> D, and t ∘ f = g ∘ s
  • (s',t'): g -> h where s': C -> E, t': D -> F, and t' ∘ g = h ∘ s'

Composition of morphisms means:

  • (s', t') ∘ (s, t) = (s' ∘ s, t' ∘ t)

The morphism from f to h is valid because (t' ∘ t) ∘ f = h ∘ (s' ∘ s).

  • Left side composition: (t' ∘ t) ∘ f = t' ∘ (t ∘ f). From the first square t ∘ f = g ∘ s, so t' ∘ (g ∘ s) = (t' ∘ g) ∘ s. From the second square t' ∘ g = h ∘ s', so (h ∘ s') ∘ s = h ∘ (s' ∘ s)

Associativity #

Suppose we have three composable morphisms

  • (s, t): f -> g
  • (s', t'): g -> h
  • (s'', t''): h -> k

Then

  • ((s'', t'') ∘ (s', t')) ∘ (s, t) = (s'' ∘ s', t'' ∘ t') ∘ (s, t) = ((s'' ∘ s') ∘ s, (t'' ∘ t') ∘ t)
  • (s'', t'') ∘ ((s', t') ∘ (s, t)) = (s'', t'') ∘ (s' ∘ s, t' ∘ t) = (s'' ∘ (s' ∘ s), t'' ∘ (t' ∘ t))

And composition of C is associative by definition

(s'' ∘ s') ∘ s = s'' ∘ (s' ∘ s) and (t'' ∘ t') ∘ t = t'' ∘ (t' ∘ t)

Therefore, composition in Arr(C) is associative.

Identity in arrow category #

Suppose we have a morphism (s, t): f -> g in Arr(C) and id as identity morphism in C.

  • Left identity: (id(C), id(D)) ∘ (s, t) = (id(C) ∘ s, id(D) ∘ t) = (s, t)
  • Right identity: (s, t) ∘ (id(A), id(B)) = (s ∘ id(A), t ∘ id(B)) = (s, t)

Both statements are valid because identities in C are identities for composition.

Or using commutative diagram

Given three original morphisms f:A -> B, Id:A -> A and ID:B -> B, the following diagram commutes.

  A ---f---> B
  |         |
 ID(A)     ID(B)
  |         |
  ▼         ▼
  A ---f---> B

ID(B)(f(x)) == f(ID(A) (x)) or ID(B) ∘ f == f ∘ ID(A). Hence we get a valid morphism that is denoted as a pair (ID(A), ID(B)). This pair is actually an identity for two reasons:

  • (ID(A), ID(B)) ∘ (h, k) == (ID(A) ∘ h, ID(B) ∘ k) - left identity
  • (h, k) ∘ (ID(A), ID(B)) == (h ∘ ID(A), k ∘ ID(B)) - right identity

Functor category #

The arrow category Arr(C) is (isomorphic to) the functor category C^[1], where [1] is the walking arrow category:

It has two objects 0, 1 and exactly one non-identity morphism u: 0 -> 1 (plus id_0, id_1). A functor F: [1] -> C picks out an arrow in C (namely F(u): F(0) -> F(1)), so functors [1] -> C correspond to arrows of C. A natural transformation between two such functors is exactly a commutative square in C, which is why morphisms in Arr(C) are commutative squares.

Arrow example #

And this is how it looks in code:

module Main (main) where

-- Define the sets as lists
aSet, bSet, cSet, dSet :: [Integer]
aSet = [1, 2]
bSet = [10, 20]
cSet = [3, 4]
dSet = [30, 40]

-- Define the functions
f :: Integer -> Integer
f 1 = 10
f 2 = 20
f _ = error "f: input not in A"

g :: Integer -> Integer
g 3 = 30
g 4 = 40
g _ = error "g: input not in C"

s :: Integer -> Integer
s 1 = 3
s 2 = 4
s _ = error "s: input not in A"

t :: Integer -> Integer
t 10 = 30
t 20 = 40
t _ = error "t: input not in B"

mapsInto :: Eq b => (a -> b) -> [a] -> [b] -> Bool
mapsInto fn domain codomain = all (`elem` codomain) (map fn domain)

-- Check commutativity for all elements in A
commutes :: Bool
commutes =
  and
    [ mapsInto f aSet bSet
    , mapsInto s aSet cSet
    , mapsInto g cSet dSet
    , mapsInto t bSet dSet
    , all (\a -> t (f a) == g (s a)) aSet
    ]

main :: IO ()
main = print commutes

// Define the sets as arrays
const A = [1, 2];
const B = [10, 20];
const C = [3, 4];
const D = [30, 40];

// Define the functions
const f = (a: number) => a === 1 ? 10 : 20;
const g = (c: number) => c === 3 ? 30 : 40;
const s = (a: number) => a === 1 ? 3 : 4;
const t = (b: number) => b === 10 ? 30 : 40;

// Check commutativity for all elements in A
const commutes = A.every(a => t(f(a)) === g(s(a)));

console.log(commutes); // Output: true

C#

using System;

class Program
{
    // Example functions (arrows)
    static int F(int a) => a + 10; // f: A -> B
    static int G(int c) => c * 10; // g: C -> D

    // s: A -> C
    static int S(int a) => a + 1;

    // t: B -> D
    static int T(int b) => (b - 9) * 10;

    static void Main()
    {
        // Pick an element a in A
        int a = 2;

        // Compute both paths in the commutative square:
        // Path 1: t(f(a))
        int path1 = T(F(a));

        // Path 2: g(s(a))
        int path2 = G(S(a));

        Console.WriteLine($"t(f({a})) = {path1}");
        Console.WriteLine($"g(s({a})) = {path2}");
        Console.WriteLine($"Commutative? {path1 == path2}");
    }
}

/*
Output:
t(f(2)) = 30
g(s(2)) = 30
Commutative? True
*/

// Diagram for reference:
//
//   A ---f---> B
//   |         |
//   s         t
//   v         v
//   C ---g---> D
//
// Here, f: A -> B, g: C -> D, s: A -> C, t: B -> D
// The square commutes if t(f(a)) == g(s(a)) for all a in A.

Key Insights #

The Arrow Category construction reveals profound insights about the nature of functions and categorical structure:

  1. Functions as Objects: The fundamental insight is that morphisms (functions) in one category can become objects in another category. This demonstrates the categorical principle that "everything can be objectified" - structure at one level becomes data at the next level.

  2. Commutative Squares as Morphisms: The morphisms in Arr(C) are not simple functions but pairs of functions (s, t) that must satisfy the commutativity condition t ∘ f = g ∘ s. This means:

    • Morphisms encode relationships between functions
    • The commutative square ensures consistency across different "paths" of computation

  3. Dual Nature of Functions: In the arrow category, functions have a dual nature:

    • As objects: They can be transformed, compared, and manipulated
    • As structure: They still encode computational relationships This duality is fundamental to higher-order programming and metaprogramming.

  4. Compositional Structure: The composition in Arr(C) is defined as (s', t') ∘ (s, t) = (s' ∘ s, t' ∘ t), which means:

    • Composition preserves the commutative property
    • The arrow category inherits associativity from the base category
    • Identity morphisms are pairs of identities: (id_A, id_B)

  5. Universal Construction: Arrow categories are a universal way to "lift" any category to a higher level where:

    • Morphisms become first-class citizens
    • Relationships between morphisms can be studied systematically

  6. Programming Implications: This construction underlies several programming concepts:

    • Higher-order functions: Functions that operate on other functions
    • Function transformers: Function decorators, and middleware
    • Program analysis: Static analysis tools that examine relationships between functions
    • Refactoring: Systematic transformations that preserve program behavior

Understanding arrow categories helps programmers:

  • Design better abstractions for function manipulation
  • Understand the theoretical foundations of functional programming
  • Recognize patterns in code transformation and optimization
  • Build more composable and modular systems

Applicability #

Arrow categories find practical applications in functional programming through various abstractions that capture the essence of composable computations with structure-preserving transformations.

In Haskell, Arrows are directly supported through the Arrow typeclass, which provides a powerful abstraction for computations that can be composed and transformed systematically.

{-# LANGUAGE Arrows #-}
import Control.Arrow
import Control.Category
import Prelude hiding (id, (.))

-- Basic Arrow example: Function arrows
-- Functions themselves form an Arrow
basicArrowExample :: IO ()
basicArrowExample = do
  putStrLn "=== Basic Function Arrows ==="

  -- arr lifts a pure function to an arrow
  let addOne = arr (+1) :: (->) Integer Integer
  let double = arr (*2) :: (->) Integer Integer
  let toString = arr show :: (->) Integer String

  -- Arrow composition using >>>
  let pipeline = addOne >>> double >>> toString

  print $ pipeline (5 :: Integer)  -- "12"

  -- First and second operate on pairs (product types)
  let pairTransform = first addOne >>> second double
  print $ pairTransform (10 :: Integer, 20 :: Integer)  -- (11, 40)

-- Arrow laws demonstration
arrowLawsExample :: IO ()
arrowLawsExample = do
  putStrLn "\n=== Arrow Laws ==="

  -- Law 1: arr id = id
  print $ (arr id :: (->) Integer Integer) (42 :: Integer)  -- 42
  print $ id (42 :: Integer)        -- 42 (same result)

  -- Law 2: arr (g . f) = arr f >>> arr g
  print $ (arr ((+3) . (*2)) :: (->) Integer Integer) (5 :: Integer)      -- 13
  print $ (arr (*2) >>> arr (+3) :: (->) Integer Integer) (5 :: Integer)  -- 13 (same result)

  -- Law 3: first (arr f) = arr (first f)
  print $ (first (arr (+1) :: (->) Integer Integer)) (10 :: Integer, 20 :: Integer)       -- (11, 20)
  print $ (arr (first (+1)) :: (->) (Integer, Integer) (Integer, Integer)) (10 :: Integer, 20 :: Integer)       -- (11, 20) (same result)

-- Arrow notation example (syntactic sugar)
arrowNotationExample :: IO ()
arrowNotationExample = do
  putStrLn "\n=== Arrow Notation ==="

  -- Using arrow notation for cleaner syntax
  let computation :: (->) Integer String
      computation = proc x -> do
        doubled <- arr (*2) -< x
        result <- arr show -< doubled
        returnA -< "Result: " ++ result

  print $ computation (21 :: Integer)  -- "Result: 42"

  -- More complex arrow computation with conditionals
  let conditionalCompute :: (->) Integer String
      conditionalCompute = proc x -> do
        doubled <- arr (*2) -< x
        if doubled > 10
          then arr ("Big: " ++) -< show doubled
          else arr ("Small: " ++) -< show doubled

  print $ conditionalCompute (3 :: Integer)   -- "Small: 6"
  print $ conditionalCompute (8 :: Integer)   -- "Big: 16"

-- Custom arrow instance for logging computations
newtype LogArrow a b = LogArrow (a -> (b, [String]))

runLogArrow :: LogArrow a b -> a -> (b, [String])
runLogArrow (LogArrow f) = f

instance Category LogArrow where
  id = LogArrow $ \x -> (x, [])
  (LogArrow g) . (LogArrow f) = LogArrow $ \x ->
    let (y, logs1) = f x
        (z, logs2) = g y
    in (z, logs1 ++ logs2)

instance Arrow LogArrow where
  arr f = LogArrow $ \x -> (f x, ["Applied function"])
  first (LogArrow f) = LogArrow $ \(x, z) ->
    let (y, logs) = f x
    in ((y, z), logs)
  second (LogArrow f) = LogArrow $ \(z, x) ->
    let (y, logs) = f x
    in ((z, y), logs)

-- Using custom LogArrow
logArrowExample :: IO ()
logArrowExample = do
  putStrLn "\n=== Custom LogArrow ==="

  let addOneLog :: LogArrow Integer Integer
      addOneLog = LogArrow $ \x -> (x + 1, ["Added 1"])
  let doubleLog :: LogArrow Integer Integer
      doubleLog = LogArrow $ \x -> (x * 2, ["Doubled"])
  let computation = addOneLog >>> doubleLog

  let (result, logs) = runLogArrow computation (5 :: Integer)
  print result  -- 12
  print logs    -- ["Added 1", "Doubled"]

main :: IO ()
main = do
  basicArrowExample
  arrowLawsExample
  arrowNotationExample
  logArrowExample

TypeScript doesn't have built-in Arrow support, but we can implement the Arrow pattern to demonstrate the concept of composable computations with structure preservation.

// Arrow interface - represents computations that can be composed
interface Arrow<A, B> {
  run(input: A): B;
  compose<C>(other: Arrow<B, C>): Arrow<A, C>;
  first<D>(): Arrow<[A, D], [B, D]>;
  second<D>(): Arrow<[D, A], [D, B]>;
}

// Basic function arrow implementation
class FunctionArrow<A, B> implements Arrow<A, B> {
  constructor(private fn: (a: A) => B) {}

  run(input: A): B {
    return this.fn(input);
  }

  compose<C>(other: Arrow<B, C>): Arrow<A, C> {
    return new FunctionArrow<A, C>(a => other.run(this.run(a)));
  }

  first<D>(): Arrow<[A, D], [B, D]> {
    return new FunctionArrow<[A, D], [B, D]>(([a, d]) => [this.run(a), d]);
  }

  second<D>(): Arrow<[D, A], [D, B]> {
    return new FunctionArrow<[D, A], [D, B]>(([d, a]) => [d, this.run(a)]);
  }
}

// Helper function to lift regular functions to arrows
const arr = <A, B>(fn: (a: A) => B): Arrow<A, B> => new FunctionArrow(fn);

// Identity arrow
const identity = <A>(): Arrow<A, A> => arr(x => x);

// Basic arrow examples
const basicArrowExamples = () => {
  console.log("=== Basic Arrow Examples ===");

  const addOne = arr((x: number) => x + 1);
  const double = arr((x: number) => x * 2);
  const toString = arr((x: number) => x.toString());

  // Arrow composition
  const pipeline = addOne.compose(double).compose(toString);
  console.log(pipeline.run(5)); // "12"

  // First and second on pairs
  const pairTransform = addOne.first<number>().compose(double.second<number>());
  console.log(pairTransform.run([10, 20])); // [11, 40]
};

// Maybe arrow for handling nullable computations
class MaybeArrow<A, B> implements Arrow<A, B | null> {
  constructor(private fn: (a: A) => B | null) {}

  run(input: A): B | null {
    return this.fn(input);
  }

  compose<C>(other: Arrow<B | null, C>): Arrow<A, C> {
    return new FunctionArrow<A, C>(a => {
      const result = this.run(a);
      return result === null ? (null as unknown as C) : other.run(result);
    });
  }

  first<D>(): Arrow<[A, D], [B | null, D]> {
    return new FunctionArrow<[A, D], [B | null, D]>(([a, d]) => [this.run(a), d]);
  }

  second<D>(): Arrow<[D, A], [D, B | null]> {
    return new FunctionArrow<[D, A], [D, B | null]>(([d, a]) => [d, this.run(a)]);
  }
}

const safeDivide = new MaybeArrow<number, number>(x => x !== 0 ? 100 / x : null);
const safeSqrt = new MaybeArrow<number | null, number>(x =>
  x === null ? null : x >= 0 ? Math.sqrt(x) : null
);

const maybeArrowExamples = () => {
  console.log("\n=== Maybe Arrow Examples ===");

  const safeComputation = safeDivide.compose(safeSqrt);

  console.log(safeComputation.run(4));  // 5
  console.log(safeComputation.run(0));  // null (division by zero)
  console.log(safeComputation.run(-1)); // null (negative input to sqrt)
};

// Logging arrow that tracks computation steps
class LoggingArrow<A, B> implements Arrow<A, B> {
  constructor(
    private fn: (a: A) => B,
    private description: string
  ) {}

  run(input: A): B {
    console.log(`Executing: ${this.description} with input ${input}`);
    const result = this.fn(input);
    console.log(`Result: ${result}`);
    return result;
  }

  compose<C>(other: Arrow<B, C>): Arrow<A, C> {
    return new FunctionArrow<A, C>(a => other.run(this.run(a)));
  }

  first<D>(): Arrow<[A, D], [B, D]> {
    return new FunctionArrow<[A, D], [B, D]>(([a, d]) => [this.run(a), d]);
  }

  second<D>(): Arrow<[D, A], [D, B]> {
    return new FunctionArrow<[D, A], [D, B]>(([d, a]) => [d, this.run(a)]);
  }
}

const loggingArrowExamples = () => {
  console.log("\n=== Logging Arrow Examples ===");

  const addOneWithLog = new LoggingArrow((x: number) => x + 1, "add one");
  const doubleWithLog = new LoggingArrow((x: number) => x * 2, "double");

  const computation = addOneWithLog.compose(doubleWithLog);
  const result = computation.run(5);
  console.log(`Final result: ${result}`);
};

// State arrow for stateful computations
class StateArrow<S, A, B> implements Arrow<A, B> {
  constructor(private fn: (state: S, input: A) => [S, B], private initialState: S) {}

  run(input: A): B {
    const [_, result] = this.fn(this.initialState, input);
    return result;
  }

  runWithState(state: S, input: A): [S, B] {
    return this.fn(state, input);
  }

  compose<C>(other: Arrow<B, C>): Arrow<A, C> {
    return new FunctionArrow<A, C>(a => other.run(this.run(a)));
  }

  first<D>(): Arrow<[A, D], [B, D]> {
    return new FunctionArrow<[A, D], [B, D]>(([a, d]) => [this.run(a), d]);
  }

  second<D>(): Arrow<[D, A], [D, B]> {
    return new FunctionArrow<[D, A], [D, B]>(([d, a]) => [d, this.run(a)]);
  }
}

const stateArrowExamples = () => {
  console.log("\n=== State Arrow Examples ===");

  // Counter arrow that increments state and adds it to input
  const counter = new StateArrow<number, number, number>(
    (state, input) => [state + 1, input + state],
    0
  );

  console.log(counter.run(10)); // 10 (0 + 10)
  console.log(counter.run(10)); // 10 (still uses initial state)

  // To see stateful behavior, we need to thread state manually
  let state = 0;
  [state, ] = counter.runWithState(state, 10);
  console.log(`State after first call: ${state}`); // 1

  const [newState, result] = counter.runWithState(state, 10);
  console.log(`Result with threaded state: ${result}`); // 11 (1 + 10)
  console.log(`New state: ${newState}`); // 2
};

// Run all examples
basicArrowExamples();
maybeArrowExamples();
loggingArrowExamples();
stateArrowExamples();

C# doesn't have native Arrow support, but we can implement the Arrow pattern using interfaces and classes to demonstrate composable computations.

using System;

// Arrow interface for composable computations
public interface IArrow<A, B>
{
    B Run(A input);
    IArrow<A, C> Compose<C>(IArrow<B, C> other);
    IArrow<Tuple<A, D>, Tuple<B, D>> First<D>();
    IArrow<Tuple<D, A>, Tuple<D, B>> Second<D>();
}

// Basic function arrow implementation
public class FunctionArrow<A, B> : IArrow<A, B>
{
    private readonly Func<A, B> function;

    public FunctionArrow(Func<A, B> function)
    {
        this.function = function;
    }

    public B Run(A input)
    {
        return function(input);
    }

    public IArrow<A, C> Compose<C>(IArrow<B, C> other)
    {
        return new FunctionArrow<A, C>(a => other.Run(this.Run(a)));
    }

    public IArrow<Tuple<A, D>, Tuple<B, D>> First<D>()
    {
        return new FunctionArrow<Tuple<A, D>, Tuple<B, D>>(
            tuple => Tuple.Create(this.Run(tuple.Item1), tuple.Item2));
    }

    public IArrow<Tuple<D, A>, Tuple<D, B>> Second<D>()
    {
        return new FunctionArrow<Tuple<D, A>, Tuple<D, B>>(
            tuple => Tuple.Create(tuple.Item1, this.Run(tuple.Item2)));
    }
}

// Helper class for creating arrows
public static class Arrow
{
    public static IArrow<A, B> Lift<A, B>(Func<A, B> function)
    {
        return new FunctionArrow<A, B>(function);
    }

    public static IArrow<A, A> Identity<A>()
    {
        return new FunctionArrow<A, A>(x => x);
    }
}

// Maybe arrow for handling nullable computations
public class MaybeArrow<A, B> : IArrow<A, B>
    where B : class?
{
    private readonly Func<A, B> function;

    public MaybeArrow(Func<A, B> function)
    {
        this.function = function;
    }

    public B Run(A input)
    {
        return function(input);
    }

    public IArrow<A, C> Compose<C>(IArrow<B, C> other)
    {
        return new FunctionArrow<A, C>(a =>
        {
            var result = this.Run(a);
            return result == null ? default(C)! : other.Run(result);
        });
    }

    public IArrow<Tuple<A, D>, Tuple<B, D>> First<D>()
    {
        return new FunctionArrow<Tuple<A, D>, Tuple<B, D>>(
            tuple => Tuple.Create(this.Run(tuple.Item1), tuple.Item2));
    }

    public IArrow<Tuple<D, A>, Tuple<D, B>> Second<D>()
    {
        return new FunctionArrow<Tuple<D, A>, Tuple<D, B>>(
            tuple => Tuple.Create(tuple.Item1, this.Run(tuple.Item2)));
    }
}

// Logging arrow that tracks computation steps
public class LoggingArrow<A, B> : IArrow<A, B>
{
    private readonly Func<A, B> function;
    private readonly string description;

    public LoggingArrow(Func<A, B> function, string description)
    {
        this.function = function;
        this.description = description;
    }

    public B Run(A input)
    {
        Console.WriteLine($"Executing: {description} with input {input}");
        var result = function(input);
        Console.WriteLine($"Result: {result}");
        return result;
    }

    public IArrow<A, C> Compose<C>(IArrow<B, C> other)
    {
        return new FunctionArrow<A, C>(a => other.Run(this.Run(a)));
    }

    public IArrow<Tuple<A, D>, Tuple<B, D>> First<D>()
    {
        return new FunctionArrow<Tuple<A, D>, Tuple<B, D>>(
            tuple => Tuple.Create(this.Run(tuple.Item1), tuple.Item2));
    }

    public IArrow<Tuple<D, A>, Tuple<D, B>> Second<D>()
    {
        return new FunctionArrow<Tuple<D, A>, Tuple<D, B>>(
            tuple => Tuple.Create(tuple.Item1, this.Run(tuple.Item2)));
    }
}

// State arrow for stateful computations
public class StateArrow<S, A, B> : IArrow<A, B>
{
    private readonly Func<S, A, Tuple<S, B>> function;
    private readonly S initialState;

    public StateArrow(Func<S, A, Tuple<S, B>> function, S initialState)
    {
        this.function = function;
        this.initialState = initialState;
    }

    public B Run(A input)
    {
        return RunWithState(initialState, input).Item2;
    }

    public Tuple<S, B> RunWithState(S state, A input)
    {
        return function(state, input);
    }

    public IArrow<A, C> Compose<C>(IArrow<B, C> other)
    {
        return new FunctionArrow<A, C>(a => other.Run(this.Run(a)));
    }

    public IArrow<Tuple<A, D>, Tuple<B, D>> First<D>()
    {
        return new FunctionArrow<Tuple<A, D>, Tuple<B, D>>(
            tuple => Tuple.Create(this.Run(tuple.Item1), tuple.Item2));
    }

    public IArrow<Tuple<D, A>, Tuple<D, B>> Second<D>()
    {
        return new FunctionArrow<Tuple<D, A>, Tuple<D, B>>(
            tuple => Tuple.Create(tuple.Item1, this.Run(tuple.Item2)));
    }
}

class Program
{
    static void BasicArrowExamples()
    {
        Console.WriteLine("=== Basic Arrow Examples ===");

        var addOne = Arrow.Lift<int, int>(x => x + 1);
        var double_ = Arrow.Lift<int, int>(x => x * 2);
        var toString = Arrow.Lift<int, string>(x => x.ToString());

        // Arrow composition
        var pipeline = addOne.Compose(double_).Compose(toString);
        Console.WriteLine(pipeline.Run(5)); // "12"

        // First and second on tuples
        var pairTransform = addOne.First<int>().Compose(double_.Second<int>());
        Console.WriteLine(pairTransform.Run(Tuple.Create(10, 20))); // (11, 40)
    }

    static void MaybeArrowExamples()
    {
        Console.WriteLine("\n=== Maybe Arrow Examples ===");

        var safeDivide = new MaybeArrow<double, string?>(x =>
            x != 0 ? (100 / x).ToString() : null);

        Console.WriteLine(safeDivide.Run(4) ?? "null");  // "25"
        Console.WriteLine(safeDivide.Run(0) ?? "null");  // "null"

        // Chain operations with error handling
        var processNumber = new MaybeArrow<string?, string?>(s =>
            s is null ? null : $"Processed: {s}");

        var pipeline = safeDivide.Compose(processNumber);
        Console.WriteLine(pipeline.Run(4) ?? "null");  // "Processed: 25"
        Console.WriteLine(pipeline.Run(0) ?? "null");  // "null"
    }

    static void LoggingArrowExamples()
    {
        Console.WriteLine("\n=== Logging Arrow Examples ===");

        var addOneWithLog = new LoggingArrow<int, int>(x => x + 1, "add one");
        var doubleWithLog = new LoggingArrow<int, int>(x => x * 2, "double");

        var computation = addOneWithLog.Compose(doubleWithLog);
        var result = computation.Run(5);
        Console.WriteLine($"Final result: {result}");
    }

    static void StateArrowExamples()
    {
        Console.WriteLine("\n=== State Arrow Examples ===");

        // Counter arrow that increments state and adds it to input
        var counter = new StateArrow<int, int, int>(
            (state, input) => Tuple.Create(state + 1, input + state),
            0);

        Console.WriteLine(counter.Run(10)); // 10 (0 + 10)

        // Stateful computation example
        var state = 0;
        var result1 = counter.RunWithState(state, 10);
        Console.WriteLine($"Result: {result1.Item2}, New State: {result1.Item1}"); // Result: 10, State: 1

        var result2 = counter.RunWithState(result1.Item1, 10);
        Console.WriteLine($"Result: {result2.Item2}, New State: {result2.Item1}"); // Result: 11, State: 2
    }

    // Practical example: HTTP request pipeline with error handling
    static void PracticalExample()
    {
        Console.WriteLine("\n=== Practical HTTP Pipeline Example ===");

        var validateUrl = new MaybeArrow<string, string>(url =>
            Uri.TryCreate(url, UriKind.Absolute, out _) ? url : "Invalid URL");

        var makeRequest = new LoggingArrow<string, string>(url =>
            $"Response from {url}", "HTTP request");

        var parseJson = new LoggingArrow<string, string>(response =>
            $"Parsed: {response}", "JSON parsing");

        // Note: In a real implementation, we'd need more sophisticated error handling
        // This demonstrates the concept

        Console.WriteLine("Arrows enable:");
        Console.WriteLine("- Composable computation pipelines");
        Console.WriteLine("- Structure-preserving transformations");
        Console.WriteLine("- Systematic error handling");
        Console.WriteLine("- Reusable computation patterns");
    }

    static void Main(string[] args)
    {
        BasicArrowExamples();
        MaybeArrowExamples();
        LoggingArrowExamples();
        StateArrowExamples();
        PracticalExample();
    }
}

Visualizing arrow categories #

0. Walking arrow category [1]

[1] has two objects (0 and 1) and exactly one non-identity morphism
u: 0 → 1 (plus identities).

0 ----u----> 1
|           |
id_0        id_1
|           |
▼           ▼
0           1

Composition laws:
  u ∘ id_0 = u
  id_1 ∘ u = u

1. Basic Structure

Original Category C:              Arrow Category Arr(C):

A ----f----> B                   [f: A→B] --------> [g: C→D]
             |                      ^                 ^
             h                      |                 |
             |                   Objects          Objects
             ▼                   (arrows           (arrows
C ----g----> D                   from C)          from C)


2. Morphisms as Commutative Squares

A morphism α: f → g in Arr(C) is a pair (s: A → C, t: B → D) such that the square commutes:

Morphism α = (s, t): f → g

A ----f----> B
|            |
s     α      t     ← This entire square is the morphism α
|            |
▼            ▼
C ----g----> D

Commutativity condition: t ∘ f = g ∘ s

Step-by-step:

Step 1: Start with two arrows f and g
   A ----f----> B     C ----g----> D

Step 2: Find connecting morphisms s and t
   A            B
   |            |
   s            t
   |            |
   ▼            ▼
   C            D

Step 3: Verify commutativity
   A ----f----> B
   |            |
   s    CHECK   t    ← Does t∘f = g∘s ?
   |            |
   ▼            ▼
   C ----g----> D


3. Composition of Morphisms

Given two morphisms α: f → g and β: g → h, their composition β ∘ α: f → h is visualized as:

First morphism α = (s₁, t₁): f → g

A ----f----> B
|            |
s₁           t₁
|            |
▼            ▼
C ----g----> D

Second morphism β = (s₂, t₂): g → h

C ----g----> D
|            |
s₂           t₂
|            |
▼            ▼
E ----h----> F

Composition β ∘ α = (s₂ ∘ s₁, t₂ ∘ t₁): f → h

A ----f----> B
|            |
s₂∘s₁       t₂∘t₁
|            |
▼            ▼
E ----h----> F

Extended composition diagram:

A ----f----> B
|            |
s₁           t₁
|            |
▼            ▼
C ----g----> D
|            |
s₂           t₂
|            |
▼            ▼
E ----h----> F

Final composed morphism: (s₂∘s₁, t₂∘t₁): f → h


4. Identity Morphisms

For any arrow f: A → B, the identity morphism id_f is the pair (id_A, id_B):

Identity morphism id_f = (id_A, id_B): f → f

A ----f----> B
|            |
id_A    ✓    id_B   ← Trivially commutes
|            |
▼            ▼
A ----f----> B

Verification: id_B ∘ f = f = f ∘ id_A ✓

5. Complex Composition Example

Consider a chain of three morphisms in the original category:

Original morphisms:
f: A → B,  g: B → C,  h: C → D

Arrow category objects:
[f], [g], [h]

Possible morphisms between them:

Morphism α: f → g

A ----f----> B
|            |
f      α     g
|            |
▼            ▼
B ----g----> C

Morphism β: g → h

B ----g----> C
|            |
g      β     h
|            |
▼            ▼
C ----h----> D

Composed morphism β ∘ α: f → h

A ----f----> B
|            |
g∘f   β∘α   h∘g
|            |
▼            ▼
C ----h----> D

6. Programming Analogy

Original Category (Types and Functions):
String ----length----> Int ----square----> Int

Arrow Category (Function Transformations):
[length] -----------------> [square]
   ↑                           ↑
   |                           |
Objects are                Objects are
functions                  functions

Morphism between them:
String ----length----> Int
  |                     |
  length             square    ← (length, square): length → square
  |                     |
  ▼                     ▼
Int   ----square----> Int

Conclusion #

The Arrow pattern provides:

  • Composability: Arrows can be systematically composed to build complex computations from simple parts
  • Structure Preservation: The first and second operations preserve the structure of product types
  • Error Handling: Maybe/Option arrows handle null values gracefully
  • Logging/Tracing: Logging arrows add observability without changing computation logic
  • State Management: State arrows thread state through computations
  • Modularity: Each arrow encapsulates a specific aspect of computation
  • Reusability: Arrows can be reused and recombined in different contexts

The Arrow pattern is particularly useful for building robust, composable systems where computations need to be combined while preserving their essential structure and properties.

Source code #

Reference implementation

References

  1. Arrow categories ·
  2. Functor category (Wikipedia) ·
  3. Commutative diagram (Wikipedia) ·