Kleisli category

 _  ___     _____ ___ ____  _     ___
| |/ / |   | ____|_ _/ ___|| |   |_ _|
| ' /| |   |  _|  | |\___ \| |    | |
| . \| |___| |___ | | ___) | |___ | |
|_|\_\_____|_____|___|____/|_____|___|__  ___ _____ ____
 / ___|  / \|_   _| ____/ ___|/ _ \|  _ \|_ _| ____/ ___|
| |     / _ \ | | |  _|| |  _| | | | |_) || ||  _| \___ \
| |___ / ___ \| | | |__| |_| | |_| |  _ < | || |___ ___) |
 \____/_/   \_\_| |_____\____|\___/|_| \_\___|_____|____/

We have been talking a lot about monads recently. We looked at their properties, usage, best practices. But how do they fit into category theory? We know about their relationship to monoids.

Semigroup  -->  Monoid
                        \
                         \
                          ---> Monad <---- Natural transformation
                         /\
Functor --> Applicative    \
                           Endofunctor

Guess what. That's not all. All the concepts that we introduced tend to find their place among the rest in a form of a classification. And monads are not the exception. Yes, we are going to be talking about the categories again...

Every monad gives rise to a Kleisli category. And that is the missing piece that forms the full circle.

Kleisli category #

Remember when we learned that a category consists of objects, morphisms between objects, and rules for composition? Well, every monad gives rise to a special category called its Kleisli category, where:

• Objects are the same as in the original category
• Morphisms are "monadic functions" of the form a -> M b (where M is our monad)
• Composition is defined using the monad's bind operation

It means that when you write flatMap or >>= in your code, you're actually performing categorical composition in the Kleisli category!

Think about all those monadic functions you've written:

• String -> Maybe Int (parsing that might fail)
• UserId -> IO User (database lookup with side effects)
• Config -> State AppState String (stateful computations)

Each of these has the shape a -> M b, and it turns out they form morphisms in a category. When you chain them together with monadic bind, you're composing morphisms in the Kleisli category. The monad laws we learned? They're just the category laws in disguise!

This connection explains why the monad laws ensure that composition works as expected. It's because monads are secretly categories, and we've been doing category theory all along without realizing it.

Formal definition #

Given a category C and a monad T = (T, η, μ) (definition) on C, where T: C -> C is an endofunctor, η: Id_C ⟹ T is unit, and μ: T ∘ T ⟹ T is multiplication, the Kleisli category C_T (also denoted Kl(T)) is defined as follows:

1. Objects: The objects of C_T are the same as the objects of C. If A is an object in C, then A is also an object in C_T.

2. Morphisms: The morphisms in C_T are different from those in C:

• A morphism from object A to object B in C_T is a morphism f: A -> TB in the original category C
• We write this as f: A -> B in C_T to distinguish Kleisli morphisms from regular morphisms

In other words: Hom_{C_T}(A, B) = Hom_C(A, TB)

Identity Morphisms #

For each object A in C_T, the identity morphism id_A: A -> A is defined as:

id_A = η_A: A -> TA

where η_A is the unit of the monad T at object A.

Composition #

Given two Kleisli morphisms:

• f: A -> B (which is f: A -> TB in C)
• g: B -> C (which is g: B -> TC in C)

Their composition g ∘_T f: A -> C is defined as:

• g ∘_T f = μ_C ∘ T(g) ∘ f: A -> TC

where:

• μ_C: TTC -> TC is the multiplication (join) of the monad at object C
• T(g): TB -> TTC is the functor T applied to morphism g

Composition in Terms of Bind #

In programming terms, if we have:

• f: A -> M B
• g: B -> M C

Then their Kleisli composition is: g ∘_T f = λx. f(x) >>= g

or equivalently: g ∘_T f = λx. flatMap(f(x), g)

Category Laws #

The Kleisli category satisfies the category laws because of the monad laws:

Left Identity: id_B ∘_T f = f

• Follows from the right unit law: μ ∘ Tη = id

Right Identity: f ∘_T id_A = f

• Follows from the left unit law: μ ∘ ηT = id

Associativity: (h ∘_T g) ∘_T f = h ∘_T (g ∘_T f)

• Follows from the associativity law: μ ∘ Tμ = μ ∘ μT

Set category example #

Sets form categories like so:

• Objects: All sets (collections of elements) Examples: ℕ (natural numbers), ℝ (real numbers), {1, 2, 3}, ∅ (empty set), etc.

• Morphisms: Functions between sets A morphism from set A to set B is a function f: A -> B Each element in A maps to exactly one element in B

• Identity Morphisms For each set A, the identity function id_A: A -> A id_A(x) = x for all x ∈ A

• Composition Function composition: if f: A -> B and g: B -> C, then g ∘ f: A -> C (g ∘ f)(x) = g(f(x))

• Category Laws

  • Left Identity: id_B ∘ f = f
  • Right Identity: f ∘ id_A = f
  • Associativity: h ∘ (g ∘ f) = (h ∘ g) ∘ f

In the category Set with the Maybe monad, Kleisli category looks like this:

• Objects: All sets (same as in Set)
• Morphisms A -> B: Functions A -> Maybe B
• Identity: η_A(x) = Some(x)
• Composition: (g ∘_T f)(x) = f(x) >>= g

Kleisli Arrow #

Now that we understand the formal structure, let's dive deeper into the key concept that makes Kleisli categories work: the Kleisli arrow.

A Kleisli arrow is simply a function of the form A -> M B, where:

• A is the input type
• B is the output type
• M is a monad

These arrows are the building blocks of the Kleisli category. Every morphism in a Kleisli category is a Kleisli arrow.

Let's see how regular functions transform into Kleisli arrows:

Regular function composition:

f: A -> B g: B -> C g ∘ f: A -> C

Kleisli arrow composition:

f: A -> M B (Kleisli arrow) g: B -> M C (Kleisli arrow) g <=< f: A -> M C (Kleisli composition)

The key difference is that Kleisli arrows can "fail", have "side effects", or produce "multiple results" - depending on the monad M.

Kleisli Composition Operator #

In Haskell notation, a Kleisli arrow looks like this:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

There is a special built-in operator for Kleisli composition: <=< (read as "fish")

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(g <=< f) x = f x >>= g

This is the "flipped" version of bind that makes the composition direction match mathematical notation.

Examples of Kleisli Arrows #

Partial Functions (Maybe monad)

parseInt :: String -> Maybe Int
sqrt :: Int -> Maybe Int

-- Composition: parse then take square root
parseAndSqrt :: String -> Maybe Int
parseAndSqrt = sqrt <=< parseInt

Effectful Functions (IO monad)

readUserId :: () -> IO Int
fetchUser :: Int -> IO User

-- Composition: read ID then fetch user
getUserFromInput :: () -> IO User
getUserFromInput = fetchUser <=< readUserId

Stateful Functions (State monad)

incrementCounter :: () -> State Int Int
doubleValue :: Int -> State Int Int

-- Composition: increment then double
incAndDouble :: () -> State Int Int
incAndDouble = doubleValue <=< incrementCounter

Kleisli Extension #

Kleisli arrows represent a shift in thinking:

• Regular functions: Pure transformations A -> B
• Kleisli arrows: Computations that produce B from A in context M

This perspective is powerful because it lets us treat "computations" as first-class objects that can be composed, analyzed, and reasoned about categorically.

But since a Kleisli arrow is just a morphism, we need something on top to extend it to monadic inputs.

The Kleisli extension is the operation that lets you lift an ordinary Kleisli arrow f: A -> T B into a monadic bind on T A.

Formally: given f: A -> T B, the Kleisli extension f*: T A -> T B is defined by f* = μ_B ∘ T f

• T f: T A -> T(T B) - apply the functor inside the monad
• μ_B: T(T B) -> T B - the monad’s multiplication or "join" at object B

In Haskell:

-- given
f :: a -> m b
-- we define
fstar :: m a -> m b
fstar ma = ma >>= f

This is exactly bind in Haskell: take a monadic value and a Kleisli arrow, and chain them.

• A Kleisli arrow is a morphism A -> T B
• The Kleisli extension takes such an arrow and extends it to work on T A

So Kleisli extension is the machinery that makes sequencing possible: it’s what turns applicative-style combination into full monadic chaining.

Kleisli Triple Definition #

There is one more tiny piece of the puzzle left. One more way to represent monads.

A monad can equivalently be defined as a Kleisli triple (M, η, (-)^*) where:

• M: Obj(C) -> Obj(C) maps objects
• η_A: A -> M(A) for each object A (unit)
• for every Kleisli arrow f: A -> M(B), the extension f*: M(A) -> M(B) lifts f to monadic inputs

The Kleisli extension satisfies:

• Left identity: f* ∘ η_A = f
• Right identity: (η_A)* = id_{M(A)}
• Associativity: g* ∘ f* = (g* ∘ f)*

Kleisli composition is then induced by extension: for f: A -> M(B) and g: B -> M(C), define g • f = g* ∘ f.

The Kleisli triple reveals that monads are fundamentally about composition. Instead of thinking about bind and return as separate operations, we see that monads are really about defining a new kind of composition (•) that handles effects automatically.

When language designers create new monadic syntax, they're essentially providing convenient ways to write Kleisli composition.

The traditional monad definition requires understanding functors, natural transformations, and complex coherence conditions. The Kleisli triple gives us the same expressive power with three simple extension laws that directly correspond to how we actually use monads in practice. The Kleisli triple makes the categorical nature of monads explicit.

Remember lax monoidal discussion we had? Back then, we established that an applicative functor is a lax monoidal functor - it can combine independent effects. And every monad is an applicative, but not every applicative is a monad. Finally, the picture is crystal clear now:

• Applicative = lax monoidal functor - can combine independent effects.
• Monad = lax monoidal functor + Kleisli extension - can chain dependent effects.

    Applicative (lax monoidal)
        │
        │  add Kleisli extension (>>=)
        ▼
      Monad

Every Kleisli triple defines a category, and every monad gives rise to a Kleisli category.

In essence, the Kleisli triple shows us that when we write:

parseAge >=> validateAge

We're not just "chaining monadic operations" - we're composing morphisms in a well-defined structure that guarantees our composition will work correctly and efficiently.

Examples #

Let's see how Kleisli arrows and Kleisli composition work in practice across different languages and monads.

Safe Division Chain #

Chain multiple division operations that might fail.

import Control.Monad

-- Kleisli arrows for safe division
safeDivide :: Double -> Double -> Maybe Double
safeDivide _ 0 = Nothing
safeDivide x y = Just (x / y)

-- Partially applied Kleisli arrows
divideBy2 :: Double -> Maybe Double
divideBy2 x = safeDivide x 2

reciprocal :: Double -> Maybe Double
reciprocal x = safeDivide 1 x

divideBy4 :: Double -> Maybe Double
divideBy4 x = safeDivide x 4

-- Kleisli composition using (<=<)
complexOperation :: Double -> Maybe Double
complexOperation = divideBy4 <=< reciprocal <=< divideBy2

-- Alternative using (>=>)
complexOperation' :: Double -> Maybe Double
complexOperation' = divideBy2 >=> reciprocal >=> divideBy4

-- Usage
main :: IO ()
main = do
    print $ complexOperation 2.0   -- Just 0.25
    print $ complexOperation 0.0   -- Nothing
    print $ complexOperation' 2.0  -- Just 0.25

// Maybe monad implementation
interface Maybe<A> {
    flatMap<B>(f: (a: A) => Maybe<B>): Maybe<B>;
    map<B>(f: (a: A) => B): Maybe<B>;
}

// Kleisli composition function
const kleisliCompose = <A, B, C>(
    f: (a: A) => Maybe<B>,
    g: (b: B) => Maybe<C>
): (a: A) => Maybe<C> => {
    return (a: A) => f(a).flatMap(g);
};

class Some<A> implements Maybe<A> {
    constructor(private value: A) { }

    flatMap<B>(f: (a: A) => Maybe<B>): Maybe<B> {
        return f(this.value);
    }

    map<B>(f: (a: A) => B): Maybe<B> {
        return new Some(f(this.value));
    }
}

class None<A> implements Maybe<A> {
    flatMap<B>(f: (a: A) => Maybe<B>): Maybe<B> {
        return new None<B>();
    }

    map<B>(f: (a: A) => B): Maybe<B> {
        return new None<B>();
    }
}

// Kleisli arrows for safe division
const safeDivide = (x: number, y: number): Maybe<number> =>
    y === 0 ? new None<number>() : new Some(x / y);

const divideBy2 = (x: number): Maybe<number> => safeDivide(x, 2);
const reciprocal = (x: number): Maybe<number> => safeDivide(1, x);
const divideBy4 = (x: number): Maybe<number> => safeDivide(x, 4);

// Kleisli composition
const complexOperation = (x: number): Maybe<number> =>
    kleisliCompose(
        kleisliCompose(divideBy2, reciprocal),
        divideBy4
    )(x);

// Usage
console.log(complexOperation(2));  // Some(0.25)
console.log(complexOperation(0));  // None

using System;

// Maybe monad implementation
public interface IMaybe<T>
{
    IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f);
    IMaybe<U> Map<U>(Func<T, U> f);
}

// Kleisli composition helper
public static class MaybeExtensions
{
    public static Func<A, IMaybe<C>> KleisliCompose<A, B, C>(
        Func<A, IMaybe<B>> f,
        Func<B, IMaybe<C>> g)
    {
        return a => f(a).FlatMap(g);
    }
}

public class Some<T> : IMaybe<T>
{
    private readonly T value;
    public Some(T value) { this.value = value; }

    public IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f)
    {
        return f(value);
    }

    public IMaybe<U> Map<U>(Func<T, U> f)
    {
        return new Some<U>(f(value));
    }

    public override string ToString() => $"Some({value})";
}

public class None<T> : IMaybe<T>
{
    public IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f)
    {
        return new None<U>();
    }

    public IMaybe<U> Map<U>(Func<T, U> f)
    {
        return new None<U>();
    }

    public override string ToString() => "None";
}

public static class Program
{
    // Kleisli arrows for safe division
    public static IMaybe<double> SafeDivide(double x, double y)
    {
        return y == 0 ? new None<double>() : new Some<double>(x / y);
    }

    public static IMaybe<double> DivideBy2(double x) => SafeDivide(x, 2);
    public static IMaybe<double> Reciprocal(double x) => SafeDivide(1, x);
    public static IMaybe<double> DivideBy4(double x) => SafeDivide(x, 4);

    // Kleisli composition
    public static IMaybe<double> ComplexOperation(double x)
    {
        return MaybeExtensions.KleisliCompose(
            MaybeExtensions.KleisliCompose<double, double, double>(DivideBy2, Reciprocal),
            DivideBy4
        )(x);
    }

    public static void Main()
    {
        Console.WriteLine(ComplexOperation(2.0));  // Some(0.25)
        Console.WriteLine(ComplexOperation(0.0));  // None
    }
}

User Validation Pipeline #

Validate user data through multiple steps, short-circuiting on the first error.

data User = User String Int String deriving Show
data ValidationError = EmptyName | InvalidAge | InvalidEmail deriving Show

-- Kleisli arrows for validation (using Either for error handling)
validateName :: String -> Either ValidationError String
validateName "" = Left EmptyName
validateName name = Right name

validateAge :: String -> Either ValidationError Int
validateAge ageStr =
    case reads ageStr of
        [(age, "")] | age >= 0 && age <= 150 -> Right age
        _ -> Left InvalidAge

validateEmail :: String -> Either ValidationError String
validateEmail email
    | '@' `elem` email = Right email
    | otherwise = Left InvalidEmail

-- Kleisli composition for user creation
createUser :: (String, String, String) -> Either ValidationError User
createUser (name, ageStr, email) = do
    validName <- validateName name
    validAge <- validateAge ageStr
    validEmail <- validateEmail email
    return $ User validName validAge validEmail

-- Usage
main :: IO ()
main = do
    print $ createUser ("Alice", "25", "alice@example.com")  -- Right (User "Alice" 25 "alice@example.com")
    print $ createUser ("", "25", "alice@example.com")      -- Left EmptyName

// Either monad implementation
interface Either<L, R> {
    flatMap<B>(f: (r: R) => Either<L, B>): Either<L, B>;
    map<B>(f: (r: R) => B): Either<L, B>;
}

class Left<L, R> implements Either<L, R> {
    constructor(private value: L) { }

    flatMap<B>(f: (r: R) => Either<L, B>): Either<L, B> {
        return new Left<L, B>(this.value);
    }

    map<B>(f: (r: R) => B): Either<L, B> {
        return new Left<L, B>(this.value);
    }
}

class Right<L, R> implements Either<L, R> {
    constructor(private value: R) { }

    flatMap<B>(f: (r: R) => Either<L, B>): Either<L, B> {
        return f(this.value);
    }

    map<B>(f: (r: R) => B): Either<L, B> {
        return new Right<L, B>(f(this.value));
    }
}

// Domain types
interface User {
    name: string;
    age: number;
    email: string;
}

type ValidationError = 'EmptyName' | 'InvalidAge' | 'InvalidEmail';

// Kleisli arrows for validation
const validateName = (name: string): Either<ValidationError, string> =>
    name === '' ? new Left('EmptyName') : new Right(name);

const validateAge = (ageStr: string): Either<ValidationError, number> => {
    const age = Number(ageStr);
    return (!Number.isInteger(age) || age < 0 || age > 150)
        ? new Left('InvalidAge')
        : new Right(age);
};

const validateEmail = (email: string): Either<ValidationError, string> =>
    email.includes('@') ? new Right(email) : new Left('InvalidEmail');

// Kleisli composition for user creation
const createUser = (name: string, ageStr: string, email: string): Either<ValidationError, User> =>
    validateName(name)
        .flatMap(validName =>
            validateAge(ageStr)
                .flatMap(validAge =>
                    validateEmail(email)
                        .map(validEmail => ({
                            name: validName,
                            age: validAge,
                            email: validEmail
                        }))
                )
        );

// Usage
console.log(createUser("Alice", "25", "alice@example.com")); // Right(User)
console.log(createUser("", "25", "alice@example.com"));     // Left('EmptyName')

using System;

// Either monad implementation
public interface IEither<L, R>
{
    IEither<L, B> FlatMap<B>(Func<R, IEither<L, B>> f);
    IEither<L, B> Map<B>(Func<R, B> f);
}

public class Left<L, R> : IEither<L, R>
{
    private readonly L value;
    public Left(L value) { this.value = value; }

    public IEither<L, B> FlatMap<B>(Func<R, IEither<L, B>> f)
    {
        return new Left<L, B>(value);
    }

    public IEither<L, B> Map<B>(Func<R, B> f)
    {
        return new Left<L, B>(value);
    }

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

public class Right<L, R> : IEither<L, R>
{
    private readonly R value;
    public Right(R value) { this.value = value; }

    public IEither<L, B> FlatMap<B>(Func<R, IEither<L, B>> f)
    {
        return f(value);
    }

    public IEither<L, B> Map<B>(Func<R, B> f)
    {
        return new Right<L, B>(f(value));
    }

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

// Domain types
public class User
{
    public string Name { get; }
    public int Age { get; }
    public string Email { get; }

    public User(string name, int age, string email)
    {
        Name = name;
        Age = age;
        Email = email;
    }

    public override string ToString() => $"User({Name}, {Age}, {Email})";
}

public enum ValidationError { EmptyName, InvalidAge, InvalidEmail }

public static class UserValidationExample
{
    // Kleisli arrows for validation
    public static IEither<ValidationError, string> ValidateName(string name)
    {
        return string.IsNullOrEmpty(name)
            ? new Left<ValidationError, string>(ValidationError.EmptyName)
            : new Right<ValidationError, string>(name);
    }

    public static IEither<ValidationError, int> ValidateAge(string ageStr)
    {
        if (!int.TryParse(ageStr, out int age) || age < 0 || age > 150)
            return new Left<ValidationError, int>(ValidationError.InvalidAge);
        return new Right<ValidationError, int>(age);
    }

    public static IEither<ValidationError, string> ValidateEmail(string email)
    {
        return email.Contains("@")
            ? new Right<ValidationError, string>(email)
            : new Left<ValidationError, string>(ValidationError.InvalidEmail);
    }

    // Kleisli composition for user creation
    public static IEither<ValidationError, User> CreateUser(string name, string ageStr, string email)
    {
        return ValidateName(name)
            .FlatMap(validName =>
                ValidateAge(ageStr)
                    .FlatMap(validAge =>
                        ValidateEmail(email)
                            .Map(validEmail => new User(validName, validAge, validEmail))
                    )
            );
    }

    public static void Main()
    {
        Console.WriteLine(CreateUser("Alice", "25", "alice@example.com")); // Right(User)
        Console.WriteLine(CreateUser("", "25", "alice@example.com"));     // Left(EmptyName)
    }
}

Triangle Kleisli example #

Let's consider a Kleisli category built from triangles where morphisms are geometric transformations that might fail or produce multiple results. Unlike regular geometric transformations, Kleisli arrows wrap results in a monad to handle uncertainty, errors, or multiple outcomes.

Original Category: Triangles with deterministic transformations Kleisli Category: Triangles with potentially failing/uncertain transformations

Objects: Different triangles in the plane

• T1: An equilateral triangle
• T2: A right triangle
• T3: An isosceles triangle
• T4: A scalene triangle

Kleisli Arrows: Transformations that might fail or produce uncertain results

Hom_Kl(T1, T2): Kleisli arrows from equilateral to right triangle

T1 (Equilateral)          Maybe(T2) (Potentially right triangle)
    △                         ⟨ |\  ⟩
   /A\                        ⟨ | \ ⟩
  / | \                       ⟨ |  \⟩
 /B___C\                      ⟨ |___\⟩
                              or Nothing

1. Kleisli arrows in Hom_Kl(T1, T2):

- attemptShear: T1 -> Maybe(T2)    (might fail if angle too steep)
- tryScale: T1 -> Maybe(T2)        (might fail if proportions impossible)
- conditionalRotate: T1 -> Maybe(T2) (succeeds only under certain conditions)

2. Self-Kleisli Arrows: `Hom_Kl(T1, T1)` - Transformations that preserve type but might fail

T1 (Equilateral triangle)          Maybe(T1)
    △                               ⟨  △  ⟩
   /A\                              ⟨ /A\ ⟩
  / | \                             ⟨/ | \⟩
 /B___C\                            ⟨B___C⟩
                                    or Nothing

3. Kleisli arrows in Hom_Kl(T1, T1):

- safeRotate: T1 -> Maybe(T1)        (rotation that might fail if constraints violated)
- validateReflect: T1 -> Maybe(T1)   (reflection that checks triangle validity)
- return/pure: T1 -> Maybe(T1)       (always succeeds: pure(triangle))
- conditionalScale: T1 -> Maybe(T1)  (scaling that might fail if size limits exceeded)

4. Kleisli Composition: Chaining potentially failing transformations

Composing Kleisli arrows:

T1 --attemptShear--> Maybe(T2) --validateRotate--> Maybe(T3)

Where:
- attemptShear ∈ Hom_Kl(T1, T2): T1 → Maybe(T2)
- validateRotate ∈ Hom_Kl(T2, T3): T2 → Maybe(T3)

5. Kleisli composition (attemptShear >=> validateRotate):

    1. Apply attemptShear to T1
        - If succeeds: get Some(T2), proceed to step 2
        - If fails: get Nothing, entire composition fails
    2. If we have Some(T2), apply validateRotate
        - If succeeds: get Some(T3)
        - If fails: get Nothing

    △     attemptShear    ⟨ |\ ⟩   validateRotate   ⟨  △  ⟩
   / \    ----------->    ⟨ | \⟩   ------------->   ⟨ / \ ⟩
  /   \                   ⟨ |  \⟩                   ⟨/   \⟩
 /_____\                  ⟨ |___\⟩                  ⟨_____⟩
   T1                    Maybe(T2)                 Maybe(T3)

Direct composition: T1 -> Maybe(T3)


6. Multiple Results with List Monad

Using List monad for non-deterministic transformations:

possibleRotations: T1 → List(T1)
    △                    [  △     △     △ ]
   /A\      ------>      [ /A\   /C\   /B\ ]
  / | \                  [/ | \ / | \ / | \]
 /B___C\                 [B___C A___B C___A ]
                         (0°)   (120°) (240°)

allReflections: T1 → List(T1)
    △                    [  △     △     △ ]
   /A\      ------>      [ /A\   /B\   /C\ ]
  / | \                  [/ | \ / | \ / | \]
 /B___C\                 [B___C A___C A___B ]
                         (across different axes)

Kleisli composition:
possibleRotations >=> allReflections: T1 → List(T1)
Produces: all combinations of rotations followed by reflections

7. Identity and Associativity in Kleisli Categories

Identity Kleisli arrow:

return/pure: T1 -> Maybe(T1)
return triangle = Some(triangle)

    △                    ⟨  △  ⟩
   /A\      return       ⟨ /A\ ⟩
  / | \    --------->    ⟨/ | \⟩
 /B___C\                 ⟨B___C⟩

For any Kleisli arrow f: T1 -> Maybe(T2):
f >=> return = f = return >=> f


Associativity

For Kleisli arrows:
- f: T1 → Maybe(T2) (attemptShear)
- g: T2 → Maybe(T3) (tryRotate)
- h: T3 → Maybe(T4) (validateScale)

Associativity: (f >=> g) >=> h = f >=> (g >=> h)

Both paths produce the same T1 → Maybe(T4) transformation:

Path 1: ((attemptShear >=> tryRotate) >=> validateScale)
Path 2: (attemptShear >=> (tryRotate >=> validateScale))

    △
   / \  f    ⟨shape⟩  g    ⟨shape⟩    h    ⟨shape⟩
  /   \ ---> ⟨  or  ⟩ ---> ⟨  or  ⟩ ---->  ⟨  or ⟩
 /_____\     ⟨Nothing⟩     ⟨Nothing⟩       ⟨Nothing⟩
   T1         Maybe(T2)     Maybe(T3)       Maybe(T4)

Visualizing Kleisli categories #

The original category C has:

• Objects: A, B, C
• Morphisms: f: A -> B, g: B -> C

The Kleisli category Kl(M) for monad M has:

• Objects: Same as C: A, B, C
• Morphisms: Kleisli arrows A -> M B, B -> M C

Original Category C:              Kleisli Category Kl(M):
Objects: A, B, C          -->     Objects: A, B, C
Morphisms: f, g           -->     Morphisms: A -> M(B), B -> M(C)

A ------f------> B                A ------f------> M(B)
        |                                 |
        |                                 | (via flatMap/bind)
        g                                 |
        |                                 v
        v                                M(C)
        C

Composition:                      Kleisli Composition:
g ∘ f : A -> C                   (B -> M(C)) <=< (A -> M(B)) : A -> M(C)

Regular function composition    g ∘ f
becomes Kleisli composition     g <=< f
using the monad's               bind/flatMap

1. Step by step:

a. Apply first Kleisli arrow

A ---------> M(B)
     f

b. Apply flatMap with second Kleisli arrow

M(B) ----flatMap(g)----> M(C)
     where g: B -> M(C)


Combined: Kleisli composition
A ---------> M(C)
   g <=< f


2. Maybe monad:

Original Category (Set):          Kleisli Category Kl(Maybe):

String ----parseInt----> Int      String ----parseInt----> Maybe(Int)
       |                                    |
       |                                    | flatMap
   toString                                 |
       |                                    v
       v                                 Maybe(String)
     String

Regular composition:              Kleisli composition:
toString ∘ parseInt               pureToString <=< parseInt
(partial if parsing fails)        (safely handles failures)

where pureToString: Int -> Maybe(String)


3. The Category Laws

a. Identity return <=< f = f = f <=< return

   A ----f----> M(B)     =     A ----f----> M(B)
      \                            ^
       \                          /
        return                return
         \                      /
          v                    /
         M(A) ----f----> M(B)


b. Associativity: (h <=< g) <=< f = h <=< (g <=< f)

   A --f--> M(B) --flatMap(g)--> M(C) --flatMap(h)--> M(D)

   Both paths yield the same result:
   A ---------> M(D)

CSV Transform Example #

New look for our CSV transform pipeline example. Let's revisit it with fresh eyes - this time seeing it as Kleisli composition in the Kleisli category.

What we thought were "monadic operations" were actually morphisms in a category:

• parseAge: String -> Maybe Int - Kleisli arrow
• validateAge: Int -> Maybe Int - Kleisli arrow
• parseEmail: String -> Maybe String - Kleisli arrow
• transformCSVRow: [String] -> Maybe Person - Kleisli arrow over a whole row

import Control.Monad

-- Domain types
data Person = Person
  { name :: String
  , age :: Int
  , email :: String
  } deriving Show

-- Kleisli arrows for CSV field transformations
parseAge :: String -> Maybe Int
parseAge str = case reads str of
  [(age', "")] -> Just age'
  _ -> Nothing

validateAge :: Int -> Maybe Int
validateAge age'
  | age' >= 0 && age' <= 150 = Just age'
  | otherwise = Nothing

parseEmail :: String -> Maybe String
parseEmail email'
  | '@' `elem` email' = Just email'
  | otherwise = Nothing

-- Creating Person from validated components - also a Kleisli arrow
createPerson :: String -> String -> String -> Maybe Person
createPerson nameStr ageStr emailStr = do
  validAge <- parseAge ageStr >>= validateAge
  validEmail <- parseEmail emailStr
  return $ Person nameStr validAge validEmail

-- Kleisli composition for complete CSV row transformation
transformCSVRow :: [String] -> Maybe Person
transformCSVRow [nameStr, ageStr, emailStr] =
  createPerson nameStr ageStr emailStr
transformCSVRow _ = Nothing

-- Alternative using Kleisli composition operators
-- Individual field processors as Kleisli arrows
processAge :: String -> Maybe Int
processAge = parseAge >=> validateAge

processEmail :: String -> Maybe String
processEmail = parseEmail

-- Complete pipeline
processCSVRow :: [String] -> Maybe Person
processCSVRow [name', age', email'] = do
  validAge <- processAge age'
  validEmail <- processEmail email'
  return $ Person name' validAge validEmail
processCSVRow _ = Nothing

-- Usage example
main :: IO ()
main = do
  let csvRows =  [
        ["Alice", "25", "alice@example.com"],
        ["Bob", "-5", "bob@example.com"],    -- Invalid age
        ["Charlie", "30", "invalid-email"],  -- Invalid email
        ["Diana", "28", "diana@example.com"]]

  let results = map transformCSVRow csvRows
  let results' = map processCSVRow csvRows
  mapM_ print results
  mapM_ print results'

  -- Output:
  -- Just (Person {name = "Alice", age = 25, email = "alice@example.com"})
  -- Nothing
  -- Nothing
  -- Just (Person {name = "Diana", age = 28, email = "diana@example.com"})

// Domain types
interface Person {
  name: string;
  age: number;
  email: string;
}

// Maybe monad implementation
interface Maybe<T> {
  flatMap<U>(f: (value: T) => Maybe<U>): Maybe<U>;
  map<U>(f: (value: T) => U): Maybe<U>;
  getOrElse(defaultValue: T): T;
}

class Some<T> implements Maybe<T> {
  constructor(private value: T) {}

  flatMap<U>(f: (value: T) => Maybe<U>): Maybe<U> {
    return f(this.value);
  }

  map<U>(f: (value: T) => U): Maybe<U> {
    return new Some(f(this.value));
  }

  getOrElse(defaultValue: T): T {
    return this.value;
  }

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

class None<T> implements Maybe<T> {
  flatMap<U>(f: (value: T) => Maybe<U>): Maybe<U> {
    return new None<U>();
  }

  map<U>(f: (value: T) => U): Maybe<U> {
    return new None<U>();
  }

  getOrElse(defaultValue: T): T {
    return defaultValue;
  }

  toString(): string {
    return "None";
  }
}

// Kleisli composition helper
const kleisliCompose = <A, B, C>(
  f: (a: A) => Maybe<B>,
  g: (b: B) => Maybe<C>
): (a: A) => Maybe<C> => {
  return (a: A) => f(a).flatMap(g);
};

// Kleisli arrows for CSV field transformations
const parseAge = (ageStr: string): Maybe<number> => {
  const age = Number(ageStr);
  return Number.isInteger(age) ? new Some(age) : new None<number>();
};

const validateAge = (age: number): Maybe<number> => {
  return (age >= 0 && age <= 150) ? new Some(age) : new None<number>();
};

const parseEmail = (email: string): Maybe<string> => {
  return email.includes('@') ? new Some(email) : new None<string>();
};

// Composed Kleisli arrows
const processAge = kleisliCompose(parseAge, validateAge);
const processEmail = parseEmail; // No additional validation needed

// CSV row transformation using Kleisli composition
const transformCSVRow = (row: string[]): Maybe<Person> => {
  if (row.length !== 3) return new None<Person>();

  const [name, ageStr, emailStr] = row;

  return processAge(ageStr)
    .flatMap(validAge =>
      processEmail(emailStr)
        .map(validEmail => ({
          name,
          age: validAge,
          email: validEmail
        }))
    );
};

// Alternative using explicit Kleisli composition
const createPerson = (name: string) => (age: number) => (email: string): Person => ({
  name,
  age,
  email
});

const transformCSVRowFunctional = (row: string[]): Maybe<Person> => {
  if (row.length !== 3) return new None<Person>();

  const [name, ageStr, emailStr] = row;

  // Using Kleisli composition to build the transformation pipeline
  return new Some(name)
    .flatMap(n =>
      processAge(ageStr)
        .flatMap(a =>
          processEmail(emailStr)
            .map(e => createPerson(n)(a)(e))
        )
    );
};

// Usage example
const csvRows = [
  ["Alice", "25", "alice@example.com"],
  ["Bob", "-5", "bob@example.com"],     // Invalid age
  ["Charlie", "30", "invalid-email"],   // Invalid email
  ["Diana", "28", "diana@example.com"]
];

const results = csvRows.map(transformCSVRow);
results.forEach(result => console.log(JSON.stringify(result)));
// Output:
// Some({"name":"Alice","age":25,"email":"alice@example.com"})
// None
// None
// Some({"name":"Diana","age":28,"email":"diana@example.com"})

using System;
using System.Linq;

// Domain types
public record Person(string Name, int Age, string Email);

// Maybe monad implementation
public interface IMaybe<T>
{
    IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f);
    IMaybe<U> Map<U>(Func<T, U> f);
    T GetOrElse(T defaultValue);
}

public class Some<T> : IMaybe<T>
{
    private readonly T value;
    public Some(T value) { this.value = value; }

    public IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f) => f(value);
    public IMaybe<U> Map<U>(Func<T, U> f) => new Some<U>(f(value));
    public T GetOrElse(T defaultValue) => value;
    public override string ToString() => $"Some({value})";
}

public class None<T> : IMaybe<T>
{
    public IMaybe<U> FlatMap<U>(Func<T, IMaybe<U>> f) => new None<U>();
    public IMaybe<U> Map<U>(Func<T, U> f) => new None<U>();
    public T GetOrElse(T defaultValue) => defaultValue;
    public override string ToString() => "None";
}

// Kleisli composition helper
public static class MaybeExtensions
{
    public static Func<A, IMaybe<C>> KleisliCompose<A, B, C>(
        Func<A, IMaybe<B>> f,
        Func<B, IMaybe<C>> g)
    {
        return a => f(a).FlatMap(g);
    }

    // LINQ support - required for query syntax
    public static IMaybe<U> Select<T, U>(this IMaybe<T> maybe, Func<T, U> selector)
    {
        return maybe.Map(selector);
    }

    public static IMaybe<U> SelectMany<T, U>(this IMaybe<T> maybe, Func<T, IMaybe<U>> selector)
    {
        return maybe.FlatMap(selector);
    }

    public static IMaybe<V> SelectMany<T, U, V>(
        this IMaybe<T> maybe,
        Func<T, IMaybe<U>> selector,
        Func<T, U, V> resultSelector)
    {
        return maybe.FlatMap(t => selector(t).Map(u => resultSelector(t, u)));
    }
}

public static class CSVTransformer
{
    // Kleisli arrows for CSV field transformations
    public static IMaybe<int> ParseAge(string ageStr)
    {
        return int.TryParse(ageStr, out int age)
            ? new Some<int>(age)
            : new None<int>();
    }

    public static IMaybe<int> ValidateAge(int age)
    {
        return (age >= 0 && age <= 150)
            ? new Some<int>(age)
            : new None<int>();
    }

    public static IMaybe<string> ParseEmail(string email)
    {
        return email.Contains("@")
            ? new Some<string>(email)
            : new None<string>();
    }

    // Composed Kleisli arrows
    public static readonly Func<string, IMaybe<int>> ProcessAge =
        MaybeExtensions.KleisliCompose<string, int, int>(ParseAge, ValidateAge);

    public static readonly Func<string, IMaybe<string>> ProcessEmail = ParseEmail;

    // CSV row transformation using Kleisli composition
    public static IMaybe<Person> TransformCSVRow(string[] row)
    {
        if (row.Length != 3) return new None<Person>();

        var (name, ageStr, emailStr) = (row[0], row[1], row[2]);

        return ProcessAge(ageStr)
            .FlatMap(validAge =>
                ProcessEmail(emailStr)
                    .Map(validEmail => new Person(name, validAge, validEmail))
            );
    }

    // Alternative using LINQ query syntax (which is Kleisli composition!)
    public static IMaybe<Person> TransformCSVRowLinq(string[] row)
    {
        if (row.Length != 3) return new None<Person>();

        var (name, ageStr, emailStr) = (row[0], row[1], row[2]);

        return
            from age in ProcessAge(ageStr)
            from email in ProcessEmail(emailStr)
            select new Person(name, age, email);
    }

    public static void Main()
    {
        var csvRows = new string[][]
        {
            new[] { "Alice", "25", "alice@example.com" },
            new[] { "Bob", "-5", "bob@example.com" },     // Invalid age
            new[] { "Charlie", "30", "invalid-email" },   // Invalid email
            new[] { "Diana", "28", "diana@example.com" }
        };

        var results = csvRows.Select(TransformCSVRow).ToArray();

        foreach (var result in results)
        {
            Console.WriteLine(result);
        }
        // Output:
        // Some(Person { Name = Alice, Age = 25, Email = alice@example.com })
        // None
        // None
        // Some(Person { Name = Diana, Age = 28, Email = diana@example.com })
    }
}

Conclusion #

Kleisli categories reveal the structure underlying everyday functional programming patterns. What initially appears as "chaining monadic operations" is actually composition of morphisms in a category.

• Every Monad Gives Rise to a Kleisli Category

• Composition Becomes Natural: Instead of manually threading effects through code, Kleisli composition provides:

  • Automatic effect handling: Failures, multiple results, and side effects propagate correctly
  • Associative composition: (f >=> g) >=> h = f >=> (g >=> h) ensures predictable behavior
  • Identity preservation: return >=> f = f = f >=> return

Understanding Kleisli categories transforms how we approach problems:

• Before: "I need to chain these operations and handle the Maybe/Either/IO effects manually"
• After: "I'm composing morphisms in the Kleisli category - the structure that guarantees correct composition"

This shift from imperative effect-handling to declarative composition leads to:

• More reliable code (category laws ensure correctness)
• Better composability (Kleisli arrows compose naturally)
• Clearer intent (the structure reveals the pattern)
• Easier testing (pure functions compose into pure pipelines)

Instead of "chaining functions", we are composing morphisms in a category that automatically handles the computational effects, ensures associativity, and provides identity elements.

Source code #

Reference implementation (opens in a new tab)

References

1. Kleisli category (opens in a new tab)
2. Arrow tutorial (opens in a new tab)
3. Functional Pearl: Kleisli arrows of outrageous fortune (opens in a new tab)

Continue exploring

• Monad I Sequencing computations in a context Shared tags: monad, functional-programming · Same collection · Same subsection
• Monad II Practical monad implementations and examples Shared tags: monad, functional-programming · Same collection · Same subsection
• MonadPlus Choice and failure for monadic computations Shared tags: monad, functional-programming · Same collection · Same subsection