Categories in programming

Categories as Programming Abstractions

Category theory provides a mathematical foundation for many programming concepts. By viewing programs through the lens of categories, we gain powerful abstractions and reasoning tools.

The Category of Types and Functions

Most programming languages naturally form a category:

  • Objects: Types (Int, String, User, etc.)
  • Morphisms: Functions between types
  • Identity: The identity function id x = x
  • Composition: Function composition (g . f)(x) = g(f(x))

Example: Haskell

-- Types as objects
type Name = String
type Age = Int
type User = (Name, Age)

-- Functions as morphisms
getName :: User -> Name
getName (name, _) = name

getAge :: User -> Age
getAge (_, age) = age

-- Identity
id :: a -> a
id x = x

-- Composition
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(g . f) x = g (f x)

Example: Python

from typing import Callable, TypeVar

A = TypeVar('A')
B = TypeVar('B')
C = TypeVar('C')

# Identity
def identity(x: A) -> A:
    return x

# Composition
def compose(g: Callable[[B], C], f: Callable[[A], B]) -> Callable[[A], C]:
    return lambda x: g(f(x))

# Usage
add_one = lambda x: x + 1
double = lambda x: x * 2

add_then_double = compose(double, add_one)
print(add_then_double(5))  # 12

Functors in Programming

A functor maps one category to another while preserving structure. In programming, functors typically map types to types and functions to functions.

Generic Containers as Functors

-- List is a functor
fmap :: (a -> b) -> [a] -> [b]
fmap = map

-- Tree is a functor
data Tree a = Leaf a | Node (Tree a) (Tree a)

instance Functor Tree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Node l r) = Node (fmap f l) (fmap f r)

# Python-style functor
class Functor:
    def fmap(self, f):
        raise NotImplementedError

class List(Functor):
    def __init__(self, items):
        self.items = items

    def fmap(self, f):
        return List([f(x) for x in self.items])

# Usage
numbers = List([1, 2, 3])
squared = numbers.fmap(lambda x: x ** 2)

Functors in Different Languages

JavaScript:

// Array is a functor via map
[1, 2, 3].map(x => x * 2)  // [2, 4, 6]

// Promise is a functor via then
Promise.resolve(5).then(x => x * 2)  // Promise(10)

Rust:

// Option is a functor via map
let x: Option<i32> = Some(5);
let y = x.map(|n| n * 2);  // Some(10)

// Result is a functor via map
let result: Result<i32, String> = Ok(5);
let doubled = result.map(|n| n * 2);  // Ok(10)

Java:

// Optional is a functor
Optional<Integer> x = Optional.of(5);
Optional<Integer> doubled = x.map(n -> n * 2);  // Optional[10]

// Stream is a functor
List<Integer> numbers = Arrays.asList(1, 2, 3);
List<Integer> doubled = numbers.stream()
    .map(n -> n * 2)
    .collect(Collectors.toList());

Monads in Different Paradigms

1. Functional Programming (Haskell)

-- Maybe monad for null safety
safeDivide :: Double -> Double -> Maybe Double
safeDivide _ 0 = Nothing
safeDivide x y = Just (x / y)

calculation :: Maybe Double
calculation = do
  a <- safeDivide 10 2
  b <- safeDivide a 0
  c <- safeDivide b 3
  return c
-- Result: Nothing (short-circuits on division by zero)

2. Imperative Programming (Async/Await)

JavaScript’s Promises are essentially the IO monad:

// Promise monad
async function fetchUserData(userId) {
  const user = await fetchUser(userId);        // bind operation
  const posts = await fetchPosts(user.id);     // sequencing
  const comments = await fetchComments(posts); // effects are composed
  return comments;
}

// Equivalent to monadic composition:
// fetchUser(userId) >>= \user ->
// fetchPosts(user.id) >>= \posts ->
// fetchComments(posts)

3. Object-Oriented Programming (Java)

// Optional monad
Optional<User> user = userRepository.findById(id);

String result = user
    .flatMap(u -> u.getEmail())      // bind
    .map(email -> email.toLowerCase()) // fmap
    .orElse("no-email@example.com");  // default value

// Stream monad
List<Integer> result = Stream.of(1, 2, 3, 4, 5)
    .flatMap(n -> Stream.of(n, n * 2))  // bind
    .filter(n -> n > 3)
    .collect(Collectors.toList());

4. Procedural Programming (Error Handling)

Even C-style error handling follows monadic patterns:

// Result type (simple Either monad)
typedef struct {
    bool is_ok;
    union {
        int value;
        const char* error;
    };
} Result;

Result divide(int x, int y) {
    if (y == 0) {
        return (Result){.is_ok = false, .error = "Division by zero"};
    }
    return (Result){.is_ok = true, .value = x / y};
}

// Monadic composition (manually)
Result calculate(int a, int b, int c) {
    Result r1 = divide(a, b);
    if (!r1.is_ok) return r1;

    Result r2 = divide(r1.value, c);
    if (!r2.is_ok) return r2;

    return r2;
}

Category Theory Patterns in Software Design

1. Composition Over Inheritance

Category theory emphasizes composition, which aligns with modern software design:

# Inheritance (less flexible)
class Animal:
    def make_sound(self):
        pass

class Dog(Animal):
    def make_sound(self):
        return "Woof"

# Composition (more flexible, categorical)
def make_sound(sound):
    def _make_sound():
        return sound
    return _make_sound

dog_sound = make_sound("Woof")
cat_sound = make_sound("Meow")

2. Middleware/Pipeline Pattern

Composing transformations is fundamental to category theory:

// Express.js middleware (function composition)
const logger = (req, res, next) => {
    console.log(`${req.method} ${req.url}`);
    next();
};

const auth = (req, res, next) => {
    if (req.headers.auth) {
        next();
    } else {
        res.status(401).send('Unauthorized');
    }
};

// Composition
app.use(logger);
app.use(auth);
app.use(handler);

3. Stream Processing

Streams are functors that support lazy evaluation:

// Java Streams follow functor/monad patterns
List<String> result = data.stream()
    .filter(x -> x > 0)           // morphism
    .map(x -> x * 2)              // functor
    .flatMap(x -> Stream.of(x, -x)) // monad
    .collect(Collectors.toList());

4. Reactive Programming

Observables are functors over time:

// RxJS Observable (functor)
const source$ = fromEvent(button, 'click');

const clicks$ = source$
    .pipe(
        map(event => event.clientX),    // functor
        filter(x => x > 100),           // filtering morphism
        debounceTime(500)               // time-based morphism
    );

Natural Transformations in Code

Natural transformations appear as polymorphic functions that work uniformly across types:

-- Natural transformation from List to Maybe
headMaybe :: [a] -> Maybe a
headMaybe []    = Nothing
headMaybe (x:_) = Just x

-- Natural transformation from Maybe to List
maybeToList :: Maybe a -> [a]
maybeToList Nothing  = []
maybeToList (Just x) = [x]

-- Natural transformation from List to List
reverse :: [a] -> [a]

In OOP:

// Natural transformation interface
interface Transform<F, G> {
    <A> G<A> apply(F<A> fa);
}

// Example: Option to List
class OptionToList implements Transform<Option, List> {
    public <A> List<A> apply(Option<A> opt) {
        return opt.isDefined()
            ? Collections.singletonList(opt.get())
            : Collections.emptyList();
    }
}

Products and Coproducts

Category theory’s products and coproducts correspond to programming constructs:

Products (AND types)

-- Tuple (product)
type Product a b = (a, b)

-- Record (product)
data User = User
    { name :: String
    , age  :: Int
    , email :: String
    }

// TypeScript product types
type User = {
    name: string;
    age: number;
    email: string;
};

Coproducts (OR types / Sum types)

-- Either (coproduct)
data Either a b = Left a | Right b

-- Multiple options
data Shape
    = Circle Double
    | Rectangle Double Double
    | Triangle Double Double Double

// TypeScript sum types (discriminated unions)
type Shape
    = { kind: 'circle', radius: number }
    | { kind: 'rectangle', width: number, height: number }
    | { kind: 'triangle', base: number, height: number };

// Rust enums (sum types)
enum Result<T, E> {
    Ok(T),
    Err(E),
}

enum Option<T> {
    Some(T),
    None,
}

Initial and Terminal Objects

Initial Object (Void/Never)

A type with no inhabitants:

-- Void type (initial object in Hask)
data Void  -- No constructors

absurd :: Void -> a
absurd v = case v of {}  -- No cases needed

// TypeScript never type
type Never = never;

function absurd(x: never): any {
    // Can never be called
}

Terminal Object (Unit)

A type with exactly one inhabitant:

-- Unit type (terminal object in Hask)
data () = ()

unit :: a -> ()
unit _ = ()

# Python None is similar
def unit(x):
    return None

Adjunctions in Programming

Adjunctions relate pairs of functors. Example: currying/uncurrying

-- Curry and uncurry form an adjunction
curry :: ((a, b) -> c) -> (a -> b -> c)
curry f a b = f (a, b)

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f (a, b) = f a b

The relationship:

Hom(A × B, C) ≅ Hom(A, C^B)

corresponds to:

-- These are equivalent
(a, b) -> c  ≅  a -> (b -> c)

Limits and Colimits

Limits (Products, Pullbacks)

-- Product as a limit
(,) :: a -> b -> (a, b)

-- Record types are limits
data Config = Config
    { host :: String
    , port :: Int
    , debug :: Bool
    }

Colimits (Coproducts, Pushouts)

-- Either as a colimit
data Either a b = Left a | Right b

-- Tagged unions
data Event
    = Click MouseEvent
    | KeyPress KeyEvent
    | Resize WindowSize

Practical Benefits

1. Composability

Functions compose naturally:

processUser :: User -> Result
processUser = formatOutput . analyzeData . validateInput

2. Reasoning About Code

Equational reasoning using laws:

-- If f and g are pure functions
fmap f . fmap g == fmap (f . g)  -- Fusion law

3. Generic Programming

Write code that works for any type satisfying the interface:

sequence :: Monad m => [m a] -> m [a]
-- Works for Maybe, List, IO, State, etc.

4. Testability

Categorical laws give you properties to test:

-- Property-based testing
prop_functor_id :: Functor f => f a -> Bool
prop_functor_id xs = fmap id xs == id xs

Exercises

  1. Identify the category formed by your favorite programming language. What are its objects and morphisms?

  2. Implement a Functor instance for a binary tree in your language of choice.

  3. Show that function composition in your language is associative by writing test cases.

  4. Design a type that represents a product of three types and implement projection functions.

  5. Design a sum type for representing different kinds of geometric shapes and implement a function to calculate area.

  6. Implement a simple monad in your language (not using built-in monadic features) and verify the monad laws.

  7. Write a natural transformation between two functors in your language.

  8. Use currying/uncurrying to convert a multi-parameter function to a chain of single-parameter functions.

  9. Implement a middleware/pipeline system using function composition.

  10. Refactor a piece of imperative code to use functors or monads, making the control flow explicit.

See:
25
25
Ready to start
Categories in programming
Session: 1 | Break: Short
Today: 0 sessions
Total: 0 sessions