Functor

 _____ _   _ _   _  ____ _____ ___  ____  ____
|  ___| | | | \ | |/ ___|_   _/ _ \|  _ \/ ___|
| |_  | | | |  \| | |     | || | | | |_) \___ \
|  _| | |_| | |\  | |___  | || |_| |  _ < ___) |
|_|    \___/|_| \_|\____| |_| \___/|_| \_\____/

Now we know how to combine smaller pieces of code into more complex structures. This gives us many different structures we can use to solve different problems. But what do we do with those structures themselves? If we just compose them, we get even more complex constructs—do those still preserve the structure of the originals and the nature of the data they hold? Every programming language provides a variety of data types, and every realistic piece of software needs many of them. Effectively, we need a way to transform one data type into another without losing its structural meaning.

From composition to mapping #

Composition within a category keeps the results (data types) in the same category. Unfortunately, we cannot stay within one category forever. We need something that transforms data from one structure (category) to another with the same or a different data type. More formally: instead of just composing within a single context, we need to systematically map functions or transformations across different contexts or structures. As a result, the data inside one structure is transformed into data of a similar or different type, but the underlying structure is preserved.

A more realistic example #

We have a map of countries. Each country contains its own network of cities and roads. Any country's map could be represented as a graph (cities as nodes, roads as edges), where a road is a directed connection from one city to another. We consider a mapping between two such country maps (graphs) that sends each city in the first country to a city in the second country and each road in the first country to a road in the second country.

If you’ve ever used map to apply a function to every element in a list, or transformed a value inside a Maybe or Option type, you’ve already encountered the idea of a functor. Functors are a central concept in category theory, providing a formal way to apply functions to values that are "inside" some kind of context or container.

What is a Functor #

In category theory, a functor is a mapping between two categories. Unless otherwise stated here, "functor" means a covariant functor (one that preserves arrow direction). It does two things:

1. Maps each object in the first category to an object in the second category.
2. Maps each morphism (arrow/function) in the first category to a morphism in the second category, in a way that preserves structure.

Formal definition #

A functor F is a mapping between two categories that:

1. Maps objects in one category to objects in another.
2. Maps morphisms (arrows) in one category to morphisms in another, while preserving:
   • Composition: F(g ∘ f) = F(g) ∘ F(f)
   • Identity: F(id_A) = id_{F(A)}

In simpler terms, a functor transforms objects and their relationships (morphisms) from one category to another while maintaining the structure of the category.

In programming #

Think of a functor as something that lets you apply a function to a value that’s wrapped in a context—like a list, a Maybe, or even a tree.

Functor Laws #

The functor laws are two rules that every functor must follow to ensure it behaves consistently and preserves the structure of a category:

Identity Law #

Mapping the identity function over a functor does nothing. fmap id = id

fmap id = id

arr.map(x => x) // is the same as arr

list.Select(x => x).ToList(); // is the same as list

Composition Law #

Mapping the composition of two functions is the same as mapping one, then the other.

fmap (g . f) = fmap g . fmap f

// In JS/TS, compare values rather than references
JSON.stringify(arr.map(x => g(f(x)))) === JSON.stringify(arr.map(f).map(g))

Func<int, int> f = x => x + 1;
Func<int, int> g = x => x * 2;

// For List<T>
var composed = list.Select(x => f(g(x))).ToList();
var chained = list.Select(g).Select(f).ToList();
// composed and chained are both [3, 5, 7]

Formally, for a functor (F):

• ∀f: A -> B, ∀g: B -> C, F(g ∘ f) = F(g) ∘ F(f)
• ∀A, F(id_A) = id_{F(A)}

Contravariant Functor Laws #

For a contravariant functor with contramap:

• contramap id = id
• contramap (g ∘ f) = contramap f ∘ contramap g

Examples #

In Haskell, the Functor type class captures this idea:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

• f is a type constructor (e.g., Maybe, [], etc.).
• fmap applies a function (a -> b) to a value wrapped in the functor f.

List and Maybe Functors

-- List functor
fmap (+1) [1, 2, 3]      -- Result: [2, 3, 4]

-- Maybe functor
fmap (+1) (Just 5)       -- Result: Just 6
fmap (+1) Nothing        -- Result: Nothing

Custom Functor: Tree

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)

-- Usage:
let tree = Node (Leaf 1) (Leaf 2)
fmap (*2) tree  -- Result: Node (Leaf 2) (Leaf 4)

Maybe Functor

-- The `Maybe` type is a functor:
fmap (++ " World") (Just "Hello")  -- Output: Just "Hello World"
fmap (++ " World") Nothing         -- Output: Nothing

In TypeScript, arrays act as functors via map:

[1, 2, 3].map(x => x + 1); // [2, 3, 4]

// Maybe-like functor
const fmap = (f, maybe) =>
  maybe == null ? null : f(maybe);

fmap(x => x + 1, 5);    // 6
fmap(x => x + 1, null); // null

Functor

type Functor<T> = {
  map: <U>(f: (x: T) => U) => Functor<U>;
  toString: () => string;
};

Maybe functor

const maybe = <T>(value: T | null | undefined): Functor<T> => ({
  map: <U>(f: (x: T) => U): Functor<U> => {
    if (value === null || value === undefined) {
      return nothing as Functor<U>;
    }
    return just(f(value as T));
  },
  toString: () =>
    value === null || value === undefined ? "Nothing" : `Just(${value})`,
});

const just = <T>(value: T): Functor<T> => maybe(value);
const nothing: Functor<never> = maybe<never>(null);

console.log(maybe(5).map(x => x + 1).toString()); // Just(6)
console.log(maybe(null).map(x => x! + 1).toString()); // Nothing

• Objects: Maybe values (just(x) or nothing())
• Morphisms: Functions like x => x + " World"
• fmap: The map method

In C#, you can use LINQ’s Select as a functor for collections:

var numbers = new List<int> { 1, 2, 3 };
var incremented = numbers.Select(x => x + 1); // [2, 3, 4]

// Maybe-like functor
int? maybe = 5;
var result = maybe.HasValue ? (int?)(maybe.Value + 1) : null; // 6

Functor

public interface IFunctor<T>
{
    IFunctor<U> Map<U>(Func<T, U> f);
}

Maybe functor

public class Maybe<T> : IFunctor<T>
{
    private readonly T value;
    private readonly bool hasValue;

    private Maybe(T value, bool hasValue)
    {
        this.value = value;
        this.hasValue = hasValue;
    }

    public static Maybe<T> Just(T value) => new Maybe<T>(value, true);
    public static Maybe<T> Nothing() => new Maybe<T>(default(T), false);

    public IFunctor<U> Map<U>(Func<T, U> f)
    {
        if (!hasValue) return Maybe<U>.Nothing();
        return Maybe<U>.Just(f(value));
    }

    public override string ToString()
    {
        return hasValue ? $"Just({value})" : "Nothing";
    }
}

// Example usage:
var justHello = Maybe<string>.Just("Hello").Map(x => x + " World"); // Just("Hello World")
var nothing = Maybe<string>.Nothing().Map(x => x + " World");       // Nothing

Console.WriteLine(justHello); // Just(Hello World)
Console.WriteLine(nothing);   // Nothing

• Objects: Maybe<T> values (Just(x) or Nothing())
• Morphisms: Functions like x => x + " World"
• fmap: The Map method

Triangle functor example #

Suppose we have two categories:

• Category 1: Triangles in the plane, with morphisms being geometric transformations (like rotation, translation).
• Category 2: Sets, with morphisms being functions between sets.

A functor can map each triangle to its set of vertices, and each geometric transformation to the corresponding function on sets of points.

How it works:

• Objects: A triangle (as a geometric shape) => The set of its three vertices (points).
• Morphisms: A transformation (like rotating a triangle) => A function that moves each vertex accordingly.

Example:

Let triangle T have vertices A, B, and C. The functor F maps T to the set {A, B, C}.

A rotation morphism r (rotating the triangle) is mapped by F to a function that rotates each point in {A, B, C}.

Category of Triangles:        Category of Sets:
Triangle T  ---r--->  T'      {A, B, C} ---F(r)---> {A', B', C'}

F(r) is the function that applies the rotation to each vertex.

This functor takes each triangle to its set of vertices, and each geometric transformation to the corresponding function on those sets—preserving the structure of composition and identity.

Formally, for transformations r₁, r₂ between triangles T → T' → T'':

• F(id_T) = id_{F(T)}
• F(r₂ ∘ r₁) = F(r₂) ∘ F(r₁)

CSV transform example #

Let's conclude with a more realistic programming example. What could be more realistic than working with boring CSV files? They need to be loaded, parsed, and transformed according to some business rules. Are functors applicable here? Definitely.

// data could be read from the file system
// const data = fs.readFileSync(filePath, 'utf8');

type Row = Record<string, string | number>;

function readCSV(data: string): Row[] {
  const [header, ...rows] = data.trim().split('\n');
  const keys = header.split(',');
  return rows.map<Row>((row) => {
    const values = row.split(',');
    // Initially all values are strings; fits Row (string | number)
    return Object.fromEntries(keys.map((k, i) => [k, values[i]])) as Row;
  });
}

// Functor: Array.prototype.map for transformation pipeline
const toNumberAge = (row: Row): Row => ({
  ...row,
  age: Number(row['age'] as string | number),
});

const addAgeGroup = (row: Row): Row => ({
  ...row,
  ageGroup: (row['age'] as number) > 30 ? 'old' : 'young',
});

const uppercaseName = (row: Row): Row => ({
  ...row,
  name: String(row['name']).toUpperCase(),
});

const pipeline: Array<(row: Row) => Row> = [
  toNumberAge,          // Convert age to number
  addAgeGroup,          // Add ageGroup
  uppercaseName,        // Uppercase name
];

// Apply pipeline to each row
function transformData(data: Row[], pipeline: Array<(row: Row) => Row>): Row[] {
  return data.map((row) => pipeline.reduce((acc, fn) => fn(acc), row));
}

// Example usage
const data: Row[] = readCSV('name,age\nAlice,25\nBob,40');
const transformed: Row[] = transformData(data, pipeline);

console.log(transformed);

In this example, we need to label people (records) according to their age group and uppercase everyone's name. Suppose the CSV file contains two columns and two rows:

name	age
Alice	25
Bob	40

In this case, the output is:

[
  { name: 'ALICE', age: 25, ageGroup: 'young' },
  { name: 'BOB', age: 40, ageGroup: 'old' }
]

• Array.map acts as the functor, preserving the array structure while transforming each row.
• The pipeline is a sequence of pure functions, each transforming the data step by step.
• This approach is reusable and composable for any CSV data transformation.

In Haskell, things look similar; you just need to instruct the compiler with explicit types.

-- CSV Transform example in Haskell using Functor (List functor)
import Data.Char (toUpper)
import Data.List.Split (splitOn)

data Person = Person
  { name     :: String
  , age      :: Int
  , ageGroup :: String
  } deriving (Show)

-- Parse CSV string into list of Person objects
readCSV :: String -> [Person]
readCSV csv =
  let (header:rows) = lines csv
      keys = splitOn "," header
      parseRow row =
        let values = splitOn "," row
            rowMap = zip keys values
            n = lookup "name" rowMap
            a = lookup "age" rowMap >>= Just . read
        in case (n, a) of
             (Just nameVal, Just ageVal) ->
               let group = if ageVal > 30 then "old" else "young"
               in Just $ Person (map toUpper nameVal) ageVal group
             _ -> Nothing
  in map (\r -> case parseRow r of
                  Just p -> p
                  Nothing -> error "Malformed row") rows

main :: IO ()
main = do
  let csv = "name,age\nAlice,25\nBob,40"
  let people = readCSV csv
  mapM_ print people

class Person
{
    public string Name { get; set; }
    public int Age { get; set; }
    public string AgeGroup { get; set; }

    public override string ToString() =>
        $"{{ name: '{Name}', age: {Age}, ageGroup: '{AgeGroup}' }}";
}

// Parse CSV file into a dictionary: column name -> list of values
Dictionary<string, List<string>> ReadCSV(string data)
{
    var lines = data.Split('\n', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
    var keys = lines[0].Split(',');
    var columns = keys.ToDictionary(k => k, k => new List<string>());

    foreach (var line in lines.Skip(1))
    {
        var values = line.Split(',', StringSplitOptions.RemoveEmptyEntries | StringSplitOptions.TrimEntries);
        for (int i = 0; i < keys.Length; i++)
        {
            columns[keys[i]].Add(values[i]);
        }
    }
    return columns;
}

  // Transform the dictionary into a list of Person objects
IEnumerable<Person> TransformData(Dictionary<string, List<string>> data)
{
    var names = data["name"];
    var ages = data["age"].Select(int.Parse).ToList();

    var people = names.Zip(ages, (name, age) => new Person
    {
        Name = name.ToUpper(),
        Age = age,
        AgeGroup = age > 30 ? "old" : "young"
    }).ToList();

    return people;
}

var data = ReadCSV("name,age\nAlice,25\nBob,40");
var people = TransformData(data);

foreach (var person in people)
{
    Console.WriteLine(person);
}

Different shades of functors #

While we've covered the basic concept of functors, there are several important variations and specializations that are worth understanding. Each type serves a different purpose and has unique properties.

Endofunctor #

An endofunctor is a functor that maps a category to itself. In other words, it's a functor F: C -> C where both the source and target categories are the same.

Most functors we encounter in programming are actually endofunctors!

When you use map on a list, Maybe, or any container type, you're working within the same category (typically the category of types and functions in your programming language).

An endofunctor F: C → C satisfies:

• Object mapping: For each object A in C, F(A) is also in C
• Morphism mapping: For each morphism f: A -> B in C, F(f): F(A) -> F(B) is also in C
• Structure preservation: F(g ∘ f) = F(g) ∘ F(f) and F(id_A) = id_{F(A)}

In Haskell, all the common functors are endofunctors in the category Hask (Haskell types and functions):

-- List endofunctor: [a] stays in the same category
fmap (+1) [1,2,3] :: [Int]  -- [2,3,4]

-- Maybe endofunctor: Maybe a stays in the same category
fmap (*2) (Just 5) :: Maybe Int  -- Just 10
fmap (*2) Nothing :: Maybe Int   -- Nothing

-- IO endofunctor: IO a stays in the same category
fmap show (return 42) :: IO String  -- IO "42"

-- Tree endofunctor: Tree a stays in the same category
data Tree a = Leaf a | Node (Tree a) (Tree a)

instance Functor Tree where
    fmap f (Leaf x) = Leaf (f x)
    fmap f (Node left right) = Node (fmap f left) (fmap f right)

-- Example usage
tree :: Tree Int
tree = Node (Leaf 1) (Node (Leaf 2) (Leaf 3))

fmap (+10) tree :: Tree Int
-- Result: Node (Leaf 11) (Node (Leaf 12) (Leaf 13))

// Array endofunctor - transforms within the same type system
const numbers = [1, 2, 3, 4];
const doubled = numbers.map(x => x * 2); // Still Array<number>

// Optional/Maybe endofunctor
class Optional<T> {
  constructor(private value: T | null) {}

  map<U>(f: (value: T) => U): Optional<U> {
    return this.value === null ?
      new Optional<U>(null) :
      new Optional(f(this.value));
  }

  static of<T>(value: T | null): Optional<T> {
    return new Optional(value);
  }

  toString(): string {
    return this.value === null ? "None" : `Some(${this.value})`;
  }
}

// Usage - all operations stay within the TypeScript type system
const opt1 = Optional.of(5).map(x => x * 2);        // Optional<number>
const opt2 = Optional.of("hello").map(s => s.length); // Optional<number>
const opt3 = Optional.of<number>(null).map(x => x + 1); // Optional<number>

console.log(opt1.toString()); // Some(10)
console.log(opt2.toString()); // Some(5)
console.log(opt3.toString()); // None

// Promise endofunctor - transforms within async context
const promise: Promise<number> = Promise.resolve(42);
const transformedPromise: Promise<string> = promise.then(x => x.toString());

transformedPromise.then(console.log);

// IEnumerable<T> endofunctor - LINQ Select
var numbers = new List<int> { 1, 2, 3, 4 };
var strings = numbers.Select(x => x.ToString()); // Still IEnumerable, different element type

// Option/Maybe endofunctor
public class Option<T>
{
    private readonly T value;
    private readonly bool hasValue;

    private Option(T value, bool hasValue)
    {
        this.value = value;
        this.hasValue = hasValue;
    }

    public static Option<T> Some(T value) => new Option<T>(value, true);
    public static Option<T> None() => new Option<T>(default(T), false);

    public Option<U> Map<U>(Func<T, U> f)
    {
        return hasValue ? Option<U>.Some(f(value)) : Option<U>.None();
    }

    public override string ToString() =>
        hasValue ? $"Some({value})" : "None";
}

// Usage - all transformations within the same type system
var opt1 = Option<int>.Some(42).Map(x => x * 2);           // Option<int>
var opt2 = Option<string>.Some("hello").Map(s => s.Length); // Option<int>
var opt3 = Option<int>.None().Map(x => x.ToString());       // Option<string>

Console.WriteLine(opt1); // Some(84)
Console.WriteLine(opt2); // Some(5)
Console.WriteLine(opt3); // None

// Task<T> endofunctor - async transformations
var task = Task.FromResult(42);
var transformedTask = task.ContinueWith(t => t.Result.ToString()); // Task<string>

Key Properties of Endofunctors #

1. Composition: Endofunctors can be composed with each other since they map to the same category.
2. Identity: The identity functor Id(A) = A is always an endofunctor.
3. Fixed Points: Endofunctors can have fixed points where F(A) ≅ A.

The ubiquity of endofunctors in programming languages reflects the fact that most data transformations happen within a consistent type system, making endofunctors the natural abstraction for containerized or contextualized computations.

Hom functors #

Hom functors are a special class of functors that arise from the Hom-sets of a category. They provide a bridge between category theory and functional programming by making the morphisms themselves into objects that can be manipulated "functorially".

Given a category C, the Hom functor Hom(A, -) takes an object A and creates a functor from C to Set (the category of sets and functions). For any object B in C, Hom(A, B) is the set of all morphisms from A to B.

There are two types of Hom functors:

• Covariant Hom functor: Hom(A, -) - fixes the source and varies the target
• Contravariant Hom functor: Hom(-, B) - varies the source and fixes the target

Covariant Hom Functor #

For a fixed object A in category C, the covariant Hom functor Hom(A, -): C -> Set:

• Object mapping: B -> Hom(A, B) (the set of morphisms from A to B)
• Morphism mapping: For f: B -> C, we get Hom(A, f): Hom(A, B) -> Hom(A, C) where Hom(A, f)(g) = f ∘ g for any g ∈ Hom(A, B)

In Haskell, the covariant Hom functor corresponds to partially applied function types:

-- Hom(A, -) corresponds to (A -> _)
-- For fixed type A = Int, we have Hom(Int, -):

-- Hom(Int, String) - functions from Int to String
toString :: Int -> String
toString = show

-- Hom(Int, Bool) - functions from Int to Bool
isEven :: Int -> Bool
isEven n = n `mod` 2 == 0

-- The functor action: fmap for (A -> _)
-- If f :: b -> c, then fmap f :: (a -> b) -> (a -> c)
-- This is just function composition!

addOne :: Int -> Int
addOne = (+1)

addOneAndShow :: Int -> String
addOneAndShow = fmap show addOne  -- Equivalent to: show . addOne

-- Example usage
main :: IO ()
main = do
  print $ toString 42      -- "42"
  print $ isEven 4         -- True
  print $ addOneAndShow 5  -- "6"

  -- Another example: transform Int -> Int into Int -> [Int]
  let singleton x = [x]
  let addOneToList = fmap singleton addOne  -- Int -> [Int]
  print $ addOneToList 10  -- [11]

// Covariant Hom functor: Hom<A, _> for fixed A
type Hom<A, B> = (a: A) => B;

// Hom(number, -) - functions from number to various types
const toStr: Hom<number, string> = (n: number) => n.toString();
const isEven: Hom<number, boolean> = (n: number) => n % 2 === 0;
const double: Hom<number, number> = (n: number) => n * 2;

// The functor action: composition
// fmap :: (b -> c) -> (a -> b) -> (a -> c)
const fmap =
  <A, B, C>(f: (b: B) => C) =>
    (g: (a: A) => B): ((a: A) => C) =>
      (a: A) => f(g(a));

// Example: transform number -> number into number -> string
const doubleToString: Hom<number, string> = fmap<number, number, string>(toStr)(double);

console.log(doubleToString(5)); // "10"

// Another example: number -> number into number -> boolean
const doubleIsEven: Hom<number, boolean> = fmap<number, number, boolean>(isEven)(double);

console.log(doubleIsEven(3)); // true (3*2=6 is even)
console.log(doubleIsEven(2)); // true (2*2=4, which is even)

// Working with arrays of functions (sets of morphisms)
const numberFunctions: Array<Hom<number, number>> = [
  (x: number) => x + 1,
  (x: number) => x * 2,
  (x: number) => x * x
];

// Apply fmap to each function in the set
const stringFunctions: Array<Hom<number, string>> =
  numberFunctions.map((f) => fmap<number, number, string>(toStr)(f));

stringFunctions.forEach((f, i) => {
  console.log(`Function ${i}(3) = "${f(3)}"`);
  // Function 0(3) = "4"
  // Function 1(3) = "6"
  // Function 2(3) = "9"
});

// Covariant Hom functor: Func<A, _> for fixed A
// Hom(int, -) - functions from int to various types

static void HomFunctorExample()
{
    // Functions in Hom(int, string)
    Func<int, string> toString = x => x.ToString();
    Func<int, string> describe = x => $"The number {x}";

    // Functions in Hom(int, bool)
    Func<int, bool> isEven = x => x % 2 == 0;
    Func<int, bool> isPositive = x => x > 0;

    // Functions in Hom(int, int)
    Func<int, int> double_ = x => x * 2;
    Func<int, int> square = x => x * x;

    // The functor action: fmap for Func<A, _>
    // fmap :: (B -> C) -> (A -> B) -> (A -> C)
    Func<Func<B, C>, Func<Func<A, B>, Func<A, C>>> FMap<A, B, C>() =>
        f => g => x => f(g(x));

    var fmap = FMap<int, int, string>();

    // Transform int -> int functions into int -> string functions
    var doubleToString = fmap(toString)(double_);
    var squareToString = fmap(toString)(square);

    Console.WriteLine(doubleToString(5)); // "10"
    Console.WriteLine(squareToString(5)); // "25"

    // Working with collections of functions (representing Hom-sets)
    var intToIntFunctions = new List<Func<int, int>> { double_, square, x => x + 1 };

    // Map all functions to int -> string
    var intToStringFunctions = intToIntFunctions
        .Select(f => fmap(toString)(f))
        .ToList();

    Console.WriteLine("Transformed functions applied to 3:");
    for (int i = 0; i < intToStringFunctions.Count; i++)
    {
        Console.WriteLine($"Function {i}(3) = \"{intToStringFunctions[i](3)}\"");
        // Function 0(3) = "6"   (double)
        // Function 1(3) = "9"   (square)
        // Function 2(3) = "4"   (add one)
    }
}

Contravariant Hom Functor #

For a fixed object B in category C, the contravariant Hom functor Hom(-, B): C^op -> Set:

• Object mapping: A -> Hom(A, B) (the set of morphisms from A to B)
• Morphism mapping: For f: A -> C, we get Hom(f, B): Hom(C, B) -> Hom(A, B) where Hom(f, B)(g) = g ∘ f for any g ∈ Hom(C, B)

-- Contravariant Hom functor: (- -> B) for fixed B
-- This is captured by the Contravariant typeclass

import Data.Functor.Contravariant

-- For fixed target type B = String, we have Hom(-, String):
newtype ToString a = ToString (a -> String)

instance Contravariant ToString where
  contramap f (ToString g) = ToString (g . f)

-- Examples of functions targeting String
showInt :: ToString Int
showInt = ToString show

showLength :: ToString String
showLength = ToString (show . length)

-- Contravariant mapping: if we have f: A -> B and g: B -> String,
-- we can create g . f: A -> String
main :: IO ()
main = do
  let ToString intToStr = showInt
  let ToString strToStr = contramap (show :: Int -> String) showLength

  print $ intToStr 42        -- "42"
  print $ strToStr 42        -- "2" (length of "42")

// Contravariant Hom functor: (- -> B) for fixed B
interface Contravariant<A> {
  contramap<B>(f: (b: B) => A): Contravariant<B>;
}

// Predicate contravariant functor: (A -> boolean)
class Predicate<A> implements Contravariant<A> {
  constructor(private predicate: (a: A) => boolean) {}

  test(value: A): boolean {
    return this.predicate(value);
  }

  contramap<B>(f: (b: B) => A): Predicate<B> {
    return new Predicate<B>((b: B) => this.predicate(f(b)));
  }
}

// Examples with target type boolean
const isPositive = new Predicate<number>(x => x > 0);
const isLongString = new Predicate<string>(s => s.length > 5);

// Contravariant mapping: transform number -> boolean into string -> boolean
// by first converting string to number
const stringToPositive = isPositive.contramap((s: string) => parseInt(s));

console.log(isPositive.test(5));           // true
console.log(isPositive.test(-3));          // false
console.log(stringToPositive.test("10"));  // true
console.log(stringToPositive.test("-5"));  // false

// Another example: Person -> boolean via Person -> number
interface Person { age: number; name: string; }
const isAdult = new Predicate<number>(age => age >= 18);
const personIsAdult = isAdult.contramap((p: Person) => p.age);

const alice: Person = { age: 25, name: "Alice" };
const bob: Person = { age: 16, name: "Bob" };

console.log(personIsAdult.test(alice)); // true
console.log(personIsAdult.test(bob));   // false

// Contravariant Hom functor implementation
public interface IContravariant<in A>
{
    IContravariant<B> Contramap<B>(Func<B, A> f);
}

// Predicate contravariant functor
public class Predicate<A> : IContravariant<A>
{
    private readonly Func<A, bool> predicate;

    public Predicate(Func<A, bool> predicate)
    {
        this.predicate = predicate;
    }

    public bool Test(A value) => predicate(value);

    public IContravariant<B> Contramap<B>(Func<B, A> f)
    {
        return new Predicate<B>(b => predicate(f(b)));
    }

    // Helper method for easier chaining
    public Predicate<B> ContramapTo<B>(Func<B, A> f)
    {
        return new Predicate<B>(b => predicate(f(b)));
    }
}

static void ContravariantExample()
{
    // Base predicates (functions targeting bool)
    var isPositive = new Predicate<int>(x => x > 0);
    var isLongString = new Predicate<string>(s => s.Length > 5);

    // Contravariant mapping: int -> bool becomes string -> bool
    var stringIsPositive = isPositive.ContramapTo<string>(s => int.Parse(s));

    Console.WriteLine(isPositive.Test(5));            // True
    Console.WriteLine(isPositive.Test(-3));           // False
    Console.WriteLine(stringIsPositive.Test("10"));   // True
    Console.WriteLine(stringIsPositive.Test("-5"));   // False

    // Person example
    var isAdult = new Predicate<int>(age => age >= 18);
    var personIsAdult = isAdult.ContramapTo<Person>(p => p.Age);

    var alice = new Person { Age = 25, Name = "Alice" };
    var bob = new Person { Age = 16, Name = "Bob" };

    Console.WriteLine($"Alice is adult: {personIsAdult.Test(alice)}"); // True
    Console.WriteLine($"Bob is adult: {personIsAdult.Test(bob)}");     // False
}

public class Person
{
    public int Age { get; set; }
    public string? Name { get; set; }
}

Key Properties of Hom Functors #

1. Representable Functors: A functor F: C -> Set is representable if it's isomorphic to some Hom(A, -) for some object A

2. Function Types: In programming languages, function types A -> B directly correspond to Hom(A, B)

Covariant Hom Functors appear in:

• Function composition: Transforming the output of functions
• Data transformations: Mapping over function results
• API design: Composing service calls and transformations

Contravariant Hom Functors appear in:

• Event handling: Adapting event handlers for different event types
• Validation: Adapting validators for different data types
• Comparisons: Adapting comparison functions for different types
• Serialization: Converting different types to the same output format

Bifunctor #

A bifunctor is a functor that operates on two arguments simultaneously. More formally, it's a functor from the product of two categories to a third category: F: C × D → E. Bifunctors are particularly important in programming because they capture the essence of operations that combine two different types.

Bifunctors model many common programming patterns where you need to transform data that has two type parameters, such as pairs, Either types, maps, and function types themselves. They provide a systematic way to apply transformations to both "sides" of a two-parameter type.

A bifunctor F: C x D -> E must satisfy:

• Object mapping: (A, B) -> F(A, B) for objects A ∈ C and B ∈ D
• Morphism mapping: For morphisms f: A -> A' in C and g: B -> B' in D: F(f, g): F(A, B) -> F(A', B')
• Functoriality: Preserves composition and identity in both arguments

In programming, bifunctors typically provide two operations:

• bimap: Apply functions to both type parameters simultaneously
• first: Apply a function to the first type parameter only
• second: Apply a function to the second type parameter only

In Haskell, the Bifunctor typeclass captures this pattern:

class Bifunctor f where
  bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
  first :: (a -> c) -> f a b -> f c b
  second :: (b -> d) -> f a b -> f a d

  -- Default implementations
  first f = bimap f id
  second g = bimap id g

-- Tuple/Pair bifunctor - the most basic example
instance Bifunctor (,) where
  bimap f g (x, y) = (f x, g y)

-- Either bifunctor - for sum types
instance Bifunctor Either where
  bimap f _ (Left x)  = Left (f x)
  bimap _ g (Right y) = Right (g y)

-- Examples using tuples
pairExample :: IO ()
pairExample = do
  let pair = (5, "hello")

  -- Transform both elements
  let both = bimap (*2) length pair          -- (10, 5)
  print both

  -- Transform only first element
  let firstOnly = first (*3) pair            -- (15, "hello")
  print firstOnly

  -- Transform only second element
  let secondOnly = second (++ "!") pair      -- (5, "hello!")
  print secondOnly

-- Examples using Either
eitherExample :: IO ()
eitherExample = do
  let leftValue = Left 42 :: Either Int String
  let rightValue = Right "world" :: Either Int String

  -- Transform both sides (but only the present one is affected)
  let leftResult = bimap (*2) length leftValue    -- Left 84
  let rightResult = bimap (*2) length rightValue  -- Right 5

  print leftResult   -- Left 84
  print rightResult  -- Right 5

-- Custom bifunctor: Tree with two different value types
data BiTree a b = BiLeaf a b | BiNode (BiTree a b) (BiTree a b)

instance Bifunctor BiTree where
  bimap f g (BiLeaf x y) = BiLeaf (f x) (g y)
  bimap f g (BiNode l r) = BiNode (bimap f g l) (bimap f g r)

treeExample :: IO ()
treeExample = do
  let tree = BiNode (BiLeaf 1 "a") (BiLeaf 2 "b")
  let transformed = bimap (*10) length tree
  print transformed  -- BiNode (BiLeaf 10 1) (BiLeaf 20 1)

// Bifunctor interface
interface Bifunctor<A, B> {
  bimap<C, D>(f: (a: A) => C, g: (b: B) => D): Bifunctor<C, D>;
  first<C>(f: (a: A) => C): Bifunctor<C, B>;
  second<D>(g: (b: B) => D): Bifunctor<A, D>;
}

// Tuple/Pair bifunctor
class Tuple<A, B> implements Bifunctor<A, B> {
  constructor(private _first: A, private _second: B) {}

  bimap<C, D>(f: (a: A) => C, g: (b: B) => D): Tuple<C, D> {
    return new Tuple(f(this._first), g(this._second));
  }

  first<C>(f: (a: A) => C): Tuple<C, B> {
    return new Tuple(f(this._first), this._second);
  }

  second<D>(g: (b: B) => D): Tuple<A, D> {
    return new Tuple(this._first, g(this._second));
  }

  toString(): string {
    return `(${this._first}, ${this._second})`;
  }
}

// Either bifunctor (sum type)
abstract class Either<A, B> implements Bifunctor<A, B> {
  abstract bimap<C, D>(f: (a: A) => C, g: (b: B) => D): Either<C, D>;
  abstract first<C>(f: (a: A) => C): Either<C, B>;
  abstract second<D>(g: (b: B) => D): Either<A, D>;

  static left<A, B>(value: A): Either<A, B> {
    return new Left(value);
  }

  static right<A, B>(value: B): Either<A, B> {
    return new Right(value);
  }
}

class Left<A, B> extends Either<A, B> {
  constructor(private value: A) { super(); }

  bimap<C, D>(f: (a: A) => C, g: (b: B) => D): Either<C, D> {
    return new Left<C, D>(f(this.value));
  }

  first<C>(f: (a: A) => C): Either<C, B> {
    return new Left<C, B>(f(this.value));
  }

  second<D>(g: (b: B) => D): Either<A, D> {
    return new Left<A, D>(this.value);
  }

  toString(): string { return `Left(${this.value})`; }
}

class Right<A, B> extends Either<A, B> {
  constructor(private value: B) { super(); }

  bimap<C, D>(f: (a: A) => C, g: (b: B) => D): Either<C, D> {
    return new Right<C, D>(g(this.value));
  }

  first<C>(f: (a: A) => C): Either<C, B> {
    return new Right<C, B>(this.value);
  }

  second<D>(g: (b: B) => D): Either<A, D> {
    return new Right<A, D>(g(this.value));
  }

  toString(): string { return `Right(${this.value})`; }
}

// Usage examples
const tupleExample = () => {
  const pair = new Tuple(5, "hello");

  console.log("Original:", pair.toString());                    // (5, hello)
  console.log("Bimap:", pair.bimap(x => x * 2, s => s.length).toString()); // (10, 5)
  console.log("First:", pair.first(x => x * 3).toString());     // (15, hello)
  console.log("Second:", pair.second(s => s + "!").toString()); // (5, hello!)
};

const eitherExample = () => {
  const leftVal = Either.left<number, string>(42);
  const rightVal = Either.right<number, string>("world");

  console.log("Left bimap:", leftVal.bimap(x => x * 2, s => s.length).toString());   // Left(84)
  console.log("Right bimap:", rightVal.bimap(x => x * 2, s => s.length).toString()); // Right(5)
};

tupleExample();
eitherExample();

// Bifunctor interface
public interface IBifunctor<A, B>
{
    IBifunctor<C, D> Bimap<C, D>(Func<A, C> f, Func<B, D> g);
    IBifunctor<C, B> First<C>(Func<A, C> f);
    IBifunctor<A, D> Second<D>(Func<B, D> g);
}

// Tuple bifunctor
public class Tuple<A, B> : IBifunctor<A, B>
{
    public A First { get; }
    public B Second { get; }

    public Tuple(A first, B second)
    {
        First = first;
        Second = second;
    }

    public IBifunctor<C, D> Bimap<C, D>(Func<A, C> f, Func<B, D> g)
    {
        return new Tuple<C, D>(f(First), g(Second));
    }

    public IBifunctor<C, B> First<C>(Func<A, C> f)
    {
        return new Tuple<C, B>(f(First), Second);
    }

    public IBifunctor<A, D> Second<D>(Func<B, D> g)
    {
        return new Tuple<A, D>(First, g(Second));
    }

    public override string ToString() => $"({First}, {Second})";
}

// Either bifunctor (discriminated union)
public abstract class Either<A, B> : IBifunctor<A, B>
{
    public abstract IBifunctor<C, D> Bimap<C, D>(Func<A, C> f, Func<B, D> g);
    public abstract IBifunctor<C, B> First<C>(Func<A, C> f);
    public abstract IBifunctor<A, D> Second<D>(Func<B, D> g);

    public static Either<A, B> Left(A value) => new Left<A, B>(value);
    public static Either<A, B> Right(B value) => new Right<A, B>(value);
}

public class Left<A, B> : Either<A, B>
{
    public A Value { get; }

    public Left(A value) { Value = value; }

    public override IBifunctor<C, D> Bimap<C, D>(Func<A, C> f, Func<B, D> g)
    {
        return new Left<C, D>(f(Value));
    }

    public override IBifunctor<C, B> First<C>(Func<A, C> f)
    {
        return new Left<C, B>(f(Value));
    }

    public override IBifunctor<A, D> Second<D>(Func<B, D> g)
    {
        return new Left<A, D>(Value);
    }

    public override string ToString() => $"Left({Value})";
}

public class Right<A, B> : Either<A, B>
{
    public B Value { get; }

    public Right(B value) { Value = value; }

    public override IBifunctor<C, D> Bimap<C, D>(Func<A, C> f, Func<B, D> g)
    {
        return new Right<C, D>(g(Value));
    }

    public override IBifunctor<C, B> First<C>(Func<A, C> f)
    {
        return new Right<C, B>(Value);
    }

    public override IBifunctor<A, D> Second<D>(Func<B, D> g)
    {
        return new Right<A, D>(g(Value));
    }

    public override string ToString() => $"Right({Value})";
}

static void BifunctorExamples()
{
    // Tuple examples
    var pair = new Tuple<int, string>(5, "hello");

    Console.WriteLine($"Original: {pair}");                                           // (5, hello)
    Console.WriteLine($"Bimap: {pair.Bimap(x => x * 2, s => s.Length)}");           // (10, 5)
    Console.WriteLine($"First: {pair.First(x => x * 3)}");                          // (15, hello)
    Console.WriteLine($"Second: {pair.Second(s => s + "!")}");                      // (5, hello!)

    // Either examples
    var leftVal = Either<int, string>.Left(42);
    var rightVal = Either<int, string>.Right("world");

    Console.WriteLine($"Left bimap: {leftVal.Bimap(x => x * 2, s => s.Length)}");   // Left(84)
    Console.WriteLine($"Right bimap: {rightVal.Bimap(x => x * 2, s => s.Length)}"); // Right(5)
}

Key Properties of Bifunctors #

1. Composition: Bifunctors preserve composition in both arguments
2. Identity: Bifunctors preserve identity in both arguments
3. Product Structure: Many bifunctors arise from categorical products

Bifunctors appear frequently in functional programming:

• Error Handling: Either<Error, Success> - transform both error and success cases
• Key–value pairs: Map<K, V> - transform both keys and values
• Validation: Result<Error, Value> - handle both failure and success paths
• Parser Results: Transform both parse errors and parsed values
• Database Results: Handle both connection errors and query results
• Network Responses: Process both HTTP errors and response data

Visualizing functors #

A functor can be depicted as a "mapping machine" that transforms both objects and arrows:

1. Functor

Category 1:               Category 2:
Objects: A, B     -->     Objects: F(A), F(B)
Morphisms: f      -->     Morphisms: F(f)


  A ---f---> B         F(A) ---F(f)---> F(B)

   Category 1                Category 2
   (Triangles)                (Sets)
   ┌──────────┐    F      ┌────────────┐
   │   T      │ ------->  │ {A, B, C}  │
   └───┬──────┘           └─────┬──────┘
       │  r                     │ F(r)
       ▼                        ▼
   ┌──────────┐    F      ┌────────────┐
   │   T'     │  -------> │ {A',B',C'} │
   └──────────┘           └────────────┘

2. Covariant Hom-functor: Hom(A, -)

Given morphism g: B → C, we get:
Hom(A, g): Hom(A, B) → Hom(A, C)

    A ----f----> B ----g---> C
    │           │           ↑
    │           │           │
    │           └─────g∘f───┘
    │                       │
    └───────────────────────┘

Hom(A, g) maps each f ∈ Hom(A, B) to g∘f ∈ Hom(A, C)

3. Contravariant Hom-functor: Hom(-, B)

Given morphism h: A' → A, we get:
Hom(h, B): Hom(A, B) → Hom(A', B)

    A'----h---> A ----f---> B
    │           │           ↑
    │           │           │
    │           └─────f∘h───┘
    │                       │
    └───────────────────────┘

Hom(h, B) maps each f ∈ Hom(A, B) to f∘h ∈ Hom(A', B)

4. Bifunctor: F(-, -)

For objects (A, B) and morphisms f: A → A', g: B → B':

       Category C × D:                     Category E:

(A, B) ----(f,g)----> (A', B')     F(A,B) --F(f,g)--> F(A',B')
   │                     │            │                  │
   │(f,id)         (id,g)│            │F(f,id)    F(id,g)│
   ▼                     ▼            ▼                  ▼
(A', B) ---(id,g)---> (A', B')     F(A',B) ---F(id,g)---> F(A',B')


Bifunctor preserves composition and identity:
- Overall: `F(f₂∘f₁, g₂∘g₁) = F(f₂, g₂) ∘ F(f₁, g₁)`
- Partially (first component): `F(f₂∘f₁, g) = F(f₂, id) ∘ F(f₁, g)`
- Partially (second component): `F(f, g₂∘g₁) = F(id, g₂) ∘ F(f, g₁)`

Example: Tuple bifunctor (,): Set × Set → Set

Objects: (Int, String) ──→ (Int, String)
Functions: (f: Int→Bool, g: String→Int) ──→ (f×g): (Int,String)→(Bool,Int)

    (5, "hello") ---(f,g)---> (True, 5)
         │                        │
         │f×id              id×g  │
         ▼                        ▼
    (True, "hello") ---id×g---> (True, 5)

Where f(5) = True and g("hello") = 5 (length)

Example: Either bifunctor: Set × Set → Set

Left case:  Left(A) ---f---> Left(A')  [g ignored]
Right case: Right(B) ---g---> Right(B') [f ignored]

    Left(42) ---bimap(×2,length)---> Left(84)
       │                                │
       │ Only f applied                 │
       ▼                                ▼
    Left(84) -----------------------> Left(84)

    Right("hi") ---bimap(×2,length)---> Right(2)
       │                                │
       │ Only g applied                 │
       ▼                                ▼
    Right(2) -----------------------> Right(2)

Conclusion #

Just like categories, functors provide abstraction and reusability. But unlike categories, functors act as bridges between categories, keeping their structure intact.

• Abstraction:

  • Functors abstract the idea of applying a function to values inside a context (e.g., containers, computations).

• Reusability:

  • Functors allow you to write generic code that works with any data structure implementing the Functor interface.

Source code #

Reference implementation (opens in a new tab)

References

1. Functor (Wikipedia) (opens in a new tab)
2. HaskellWiki - Functor (opens in a new tab)
3. Category theory - Functor (Racket CTP) (opens in a new tab)
4. Functor (functional programming) (opens in a new tab)