Domain & codomain

 ____   ___  __  __    _    ___ _   _ ____       _    _   _ ____
|  _ \ / _ \|  \/  |  / \  |_ _| \ | / ___|     / \  | \ | |  _ \
| | | | | | | |\/| | / _ \  | ||  \| \___ \    / _ \ |  \| | | | |
| |_| | |_| | |  | |/ ___ \ | || |\  |___) |  / ___ \| |\  | |_| |
|____/ \___/|_|_ |_/_/  _\_\___|_|_\_|____/_ /_/ __\_\_| \_|____/
 / ___/ _ \|  _ \ / _ \|  \/  |  / \  |_ _| \ | / ___|
| |  | | | | | | | | | | |\/| | / _ \  | ||  \| \___ \
| |__| |_| | |_| | |_| | |  | |/ ___ \ | || |\  |___) |
 \____\___/|____/ \___/|_|  |_/_/   \_\___|_| \_|____/

Imagine trying to build a computer program without knowing what types of data your functions accept or return. You'd have no way to connect functions together, no way to catch errors before runtime, and no way to reason about whether your program will work correctly. This chaos is exactly what happens in programming without the fundamental concepts of domain and codomain.

Formal Definition #

For any morphism f: A -> B in a category C:

• A is called the domain (or source) of f
• B is called the codomain (or target) of f

We write this as:

• dom(f) = A
• cod(f) = B

Key Properties #

1. Uniqueness Every morphism has exactly one domain and one codomain. This is fundamental to the structure of categories.

2. Type Safety Morphisms can only be composed when domains and codomains align properly. This prevents nonsensical compositions.

3. Identity Preservation For any object A, the identity morphism id_A has both domain and codomain equal to A:

   • dom(id_A) = A
   • cod(id_A) = A

Composition Rules #

Morphisms can be composed when their domains and codomains match appropriately:

For morphisms f: A -> B and g: B -> C:

• The codomain of f must equal the domain of g
• Their composition g ∘ f: A -> C has:
  • Domain: A (same as domain of f)
  • Codomain: C (same as codomain of g)

Composition Requirements #

For composition g ∘ f to be valid:

1. cod(f) = dom(g) - The codomain of f must match the domain of g ^[1]
2. The result has dom(g ∘ f) = dom(f) and cod(g ∘ f) = cod(g)

Examples:

In Haskell, function type signatures clearly show domains and codomains:

-- Function signature shows domain and codomain
length :: [a] -> Int
--       ^      ^
--       |      codomain (Int)
--       domain ([a] - list of any type)

show :: Int -> String
--     ^      ^
--     |      codomain (String)
--     domain (Int)

-- Composition requires matching types
showLength :: [a] -> String
showLength = show . length
--          ^   ^
--          |   domain of length: [a]
--          codomain of length: Int
--          domain of show: Int

-- Example usage
result = showLength [1,2,3,4]  -- "4"
Copy

TypeScript's type annotations make domains and codomains explicit:

// Function type annotations show domain and codomain
const parseNumber: (input: string) => number = (input) => parseInt(input);
//                 ^               ^
//                 |               codomain (number)
//                 domain (string)

const formatResult: (value: number) => string = (value) => `Result: ${value}`;
//                  ^               ^
//                  |               codomain (string)
//                  domain (number)

// Function composition
const processInput: (input: string) => string = (input) =>
  formatResult(parseNumber(input));
//            ^          ^
//            |          domain matches codomain of parseNumber
//            codomain of parseNumber matches domain of formatResult

// Example usage
console.log(processInput("42")); // "Result: 42"
Copy

C#'s Func<TInput, TOutput> delegate type clearly shows domain and codomain:

// Func<TInput, TOutput> shows domain and codomain clearly
Func<string, int> parseNumber = input => int.Parse(input);
//   ^       ^
//   |       codomain (int)
//   domain (string)

Func<int, string> formatResult = value => $"Result: {value}";
//   ^    ^
//   |    codomain (string)
//   domain (int)

// Composition using method chaining
Func<string, string> processInput = input =>
    formatResult(parseNumber(input));
//   ^       ^
//   |       codomain (string)
//   domain (string)

// Example usage
Console.WriteLine(processInput("42")); // "Result: 42"
Copy

Domain vs Range vs Image #

It's crucial to distinguish between these related but different concepts:

• Domain: The set of all possible inputs (source object)
• Codomain: The designated target object that contains all actual outputs (the image); it need not equal the image
• Range/Image: The set of actual outputs (subset of the codomain) ^[2]

// Function from numbers to strings
const numberToWord = (n) => {
  switch(n) {
    case 1: return "one";
    case 2: return "two";
    case 3: return "three";
    default: return "unknown";
  }
};

// Domain: All possible number inputs (conceptually all numbers)
// Codomain: All strings (designated target containing the image)
// Range/Image: {"one", "two", "three", "unknown"} (actual outputs)

Copy

Visualizing domain and codomain #

The arrow `f` represents the morphism, `A` is where it starts (`domain`),
and `B` is where it points (`codomain`)

    f
A -----> B
^        ^
|        |
domain   codomain


    f         g
A -----> B -----> C
^        ^        ^
|        |        |
domain   codomain domain
of f     of f     of g
         domain   codomain
         of g     of g



The composition `g ∘ f` has:

    g ∘ f
A ---------> C
^            ^
|            |
domain       codomain
of g∘f       of g∘f


Range and image:

Domain A ----f----> Codomain B
  {1,2,3}           {a,b,c,d,e}
                         ^
                    Range/Image: {a,c,e}
                    (actual outputs of f)

Usage #

Domains and codomains are fundamental to category theory because they:

1. Enable Composition Safety They ensure morphisms can only be composed when it makes categorical sense, preventing malformed compositions.

2. Support Functor Preservation Functors must preserve domain/codomain relationships:

   • If F is a functor and f: A -> B, then F(f): F(A) -> F(B)

3. Characterize Universal Properties Many categorical constructions are defined by their domain/codomain behavior with respect to other morphisms.

Type safety example #

-- This compiles because types align
validComposition :: String -> Int
validComposition = length . words
--                ^      ^
--                |      domain: String, codomain: [String]
--                domain: [String], codomain: Int

-- This does NOT compile due to type mismatch
-- invalidComposition = show . words
--                     ^    ^
--                     |    domain: String, codomain: [String]
--                     domain: Int, codomain: String
--                     MISMATCH: [String] ≠ Int


main :: IO ()
main = print (validComposition "123")
Copy

Applications #

1. API Design Clearly specifying input and output types for functions and methods.

2. Error Prevention Type systems use domain/codomain matching to prevent runtime errors.

3. Code Documentation Function signatures serve as documentation when domains and codomains are clear.

4. Refactoring Safety Type-guided refactoring relies on preserving domain/codomain relationships.

Real world #

As we mentioned before, domain and codomain have to align for type safety to work properly. It turns out, real-world applications do not always follow strict domain–codomain rules.

Partial Functions #

Partial functions are morphisms where not every element in the domain necessarily maps to an element in the codomain. This concept is crucial for understanding how real-world functions behave when they can't handle all possible inputs.

A function f: A -> B is partial if there exist elements a ∈ A for which f(a) is undefined. In contrast, a total function is defined for every element in its domain.

In programming, many operations are naturally partial:

• Division by zero
• Array access with invalid indices
• Parsing strings that might not be valid numbers
• Database queries that might return no results

Haskell — Maybe

-- Unsafe partial function (can crash)
head :: [a] -> a
head (x:_) = x
head []    = error "empty list"  -- Runtime error!

-- Safe total function using Maybe
safeHead :: [a] -> Maybe a
safeHead []     = Nothing  -- Explicit representation of "no value"
safeHead (x:_)  = Just x   -- Wrapped successful result

-- Domain: [a] (all lists)
-- Codomain: Maybe a (optional values)
-- Now it's total - every input has a defined output


main :: IO ()
main = print (safeHead "123")
Copy

TypeScript - Optional Types

// Partial function - might fail
function parseInteger(input: string): number | undefined {
  const result = parseInt(input);
  return isNaN(result) ? undefined : result;
}

// Usage with explicit null checking
const userInput = "42";
const parsed = parseInteger(userInput);
if (parsed !== undefined) {
  console.log(`Result: ${parsed * 2}`);
} else {
  console.log("Invalid input");
}

// Domain: string (all strings)
// Codomain: number | undefined (number or absence of value)
Copy

C# - Nullable Types:

// Partial function using nullable return type
static int? ParseInteger(string input)
{
    if (int.TryParse(input, out int result))
    {
        return result;
    }

    return null;  // Explicit representation of failure
}

// Usage with null checking
string userInput = "42";
int? parsed = ParseInteger(userInput);
if (parsed.HasValue)
{
    Console.WriteLine($"Result: {parsed.Value * 2}");
}
else
{
    Console.WriteLine("Invalid input");
}

// Domain: string (all strings)
// Codomain: int? (nullable integer)
Copy

Higher-Order Functions #

Higher-order functions are functions where the domain or codomain (or both) contain function types. They treat functions as first-class values that can be passed as arguments, returned as results, or stored in data structures.

map :: (a -> b) -> [a] -> [b]
--    ^      ^    ^     ^
--    |      |    |     codomain: list of b
--    |      |    domain: list of a
--    |      codomain of function parameter
--    domain of function parameter

-- The first argument has domain 'a' and codomain 'b'
-- The whole function has domain '[a]' and codomain '[b]'
Copy

Types of Higher-Order Functions #

• Functions that take functions as arguments:

-- map takes a function and applies it to each element
map :: (a -> b) -> [a] -> [b]
--    ^^^^^^^^^    ^^^    ^^^
--    function     input  output
--    argument     list   list

-- filter takes a predicate function
filter :: (a -> Bool) -> [a] -> [a]
--       ^^^^^^^^^^^    ^^^    ^^^
--       predicate      input  filtered
--       function       list   list

-- Example usage
numbers :: [Int]
numbers = [1, 2, 3, 4, 5]

doubled :: [Int]
doubled = map (*2) numbers        -- [2, 4, 6, 8, 10]

evens :: [Int]
evens = filter even numbers       -- [2, 4]
Copy

• Functions that return functions:

-- add returns a function
add :: Int -> (Int -> Int)
add x = \y -> x + y

-- Equivalent using currying
add' :: Int -> Int -> Int
add' x y = x + y

-- Both create functions:
addFive :: Int -> Int
addFive = add 5

result :: Int
result = addFive 3  -- 8

-- Domain analysis:
-- add has domain: Int
-- add has codomain: (Int -> Int) - a function type!
Copy

• Functions that both take and return functions:

-- Function composition
(.) :: (b -> c) -> (a -> b) -> (a -> c)
--    ^^^^^^^^^    ^^^^^^^    ^^^^^^^
--    function     function   resulting
--    g: b->c      f: a->b    function

-- compose takes two functions and returns their composition
compose :: (b -> c) -> (a -> b) -> (a -> c)
compose g f = \x -> g (f x)

-- Example
toString :: Int -> String
toString = show

doubleIt :: Int -> Int
doubleIt = (*2)

-- Compose them
doubleAndShow :: Int -> String
doubleAndShow = compose toString doubleIt
-- Or using the operator: doubleAndShow = toString . doubleIt

result = doubleAndShow 21  -- "42"
Copy

TypeScript - Array Methods #

// Higher-order functions are everywhere in JavaScript
const numbers: number[] = [1, 2, 3, 4, 5];

// map: (a -> b) -> Array<a> -> Array<b>
const doubled: number[] = numbers.map(x => x * 2);

// filter: (a -> boolean) -> Array<a> -> Array<a>
const evens: number[] = numbers.filter(x => x % 2 === 0);

// reduce: (accumulator -> a -> accumulator) -> accumulator -> Array<a> -> accumulator
const sum: number = numbers.reduce((acc, x) => acc + x, 0);

// Function factory - returns customized functions
function createMultiplier(factor: number): (x: number) => number {
  return (x: number) => x * factor;
}

const triple = createMultiplier(3);
const result = triple(4); // 12

console.log(result);
Copy

C# - LINQ and Delegates #

List<int> numbers = new List<int> { 1, 2, 3, 4, 5 };

// Select is map: Func<a, b> -> IEnumerable<a> -> IEnumerable<b>
var doubled = numbers.Select(x => x * 2);

// Where is filter: Func<a, bool> -> IEnumerable<a> -> IEnumerable<a>
var evens = numbers.Where(x => x % 2 == 0);

// Aggregate is reduce/fold
var sum = numbers.Aggregate(0, (acc, x) => acc + x);

// Higher-order function that returns a function
Func<int, Func<int, int>> CreateAdder = x => y => x + y;

var addTen = CreateAdder(10);
var result = addTen(5); // 15

Console.WriteLine(result);
Copy

Categorical Significance #

Higher-order functions demonstrate that in programming language categories:

1. Function types are objects - (a -> b) is an object in the category
2. Currying is natural - The isomorphism (a × b) -> c ≅ a -> (b -> c) is fundamental
3. Composition is a morphism - (.) :: (b -> c) -> (a -> b) -> (a -> c) is itself a morphism

Conclusion #

Domains and codomains are the building blocks that make category theory and functional programming work together seamlessly. They provide:

• Mathematical rigor through precise definitions
• Type safety in programming languages
• Compositional structure that enables complex systems
• Foundational concepts for advanced categorical constructions

Source code #

Reference implementation (opens in a new tab)

Notes

1. In a category, composition is defined when the codomain of the first arrow equals the domain of the second (strict equality of objects). One can also compose up to isomorphism by inserting suitable isomorphisms, but the formal rule uses equality. · Back
2. In general categories, images may require additional structure to define; in Set, the image is the usual subset of the codomain. · Back

References

1. Codomain (opens in a new tab)
2. Domain (opens in a new tab)
3. Morphism (codomain section) (opens in a new tab)