ExamplesBy LevelBy TopicLearning Paths
858 Fundamental
← 857859 →

Kleisli Composition

Functional Programming

Tutorial

The Problem

Function composition g ∘ f works for plain functions, but fails for monadic functions f: A -> Option<B> and g: B -> Option<C> — you can't compose them directly because g expects B, not Option<B>. Kleisli composition solves this: f >=> g is a function A -> Option<C> that applies f, then if Some(b), applies g(b). This enables building pipelines of fallible functions as composable building blocks. Kleisli arrows are the category-theoretic way to think about monadic computation: instead of the Kleisli category being hard to understand, think of it as "composition that handles failure automatically." Used in parser combinators, middleware chains, and validation pipelines.

🎯 Learning Outcomes

  • • Understand the Kleisli arrow: A -> M<B> where M is a monad (Option, Result, etc.)
  • • Implement kleisli_compose(f, g) returning a new function A -> Option<C>
  • • Recognize f >=> g = |a| f(a).and_then(g) — the definition
  • • Verify that Kleisli composition satisfies the monad laws (it forms a category)
  • • Apply to: pipeline building, middleware composition, parser combinator sequences

    • Code Example

    fn kleisli<A, B, C>(
    f: impl Fn(A) -> Option<B>,
    g: impl Fn(B) -> Option<C>,
) -> impl Fn(A) -> Option<C> {
    move |a| f(a).and_then(|b| g(b))
}

let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
validate("42") // Some(21)

    Key Differences

    AspectRustOCaml
    Compositionkleisli(f, g) functionf >=> g operator
    Capturemove closureImplicit capture
    Return typeimpl Fn(A) -> Option<C>'a -> 'c option
    Multiple composeManual nestingf >=> g >=> h
    AssociativityFollows from monad lawsSame
    Result variantSame pattern with ResultSame

    OCaml Approach

    OCaml's Kleisli composition: let ( >=> ) f g = fun a -> f a >>= g. The operator >=> is the "fish operator" in Haskell. let find_email_by_id = find_user >=> find_email. OCaml's partial application makes this natural: let composed = f >=> g >=> h chains three fallible functions. The associativity of >=> follows from the monad associativity law. OCaml's Fun.compose is for plain functions; >=> is for Kleisli arrows.

    Full Source

    #![allow(clippy::all)]
// Example 059: Kleisli Composition
// Kleisli arrow: A -> Option<B>, composed to build pipelines

// Approach 1: Kleisli composition function
fn kleisli<A, B, C>(
    f: impl Fn(A) -> Option<B>,
    g: impl Fn(B) -> Option<C>,
) -> impl Fn(A) -> Option<C> {
    move |a| f(a).and_then(|b| g(b))
}

fn parse_int(s: &str) -> Option<i32> {
    s.parse().ok()
}

fn check_positive(n: i32) -> Option<i32> {
    if n > 0 {
        Some(n)
    } else {
        None
    }
}

fn safe_half(n: i32) -> Option<i32> {
    if n % 2 == 0 {
        Some(n / 2)
    } else {
        None
    }
}

// Approach 2: Kleisli for Result
fn kleisli_result<A, B, C, E>(
    f: impl Fn(A) -> Result<B, E>,
    g: impl Fn(B) -> Result<C, E>,
) -> impl Fn(A) -> Result<C, E> {
    move |a| f(a).and_then(|b| g(b))
}

fn parse_r(s: &str) -> Result<i32, String> {
    s.parse().map_err(|_| "parse failed".into())
}

fn positive_r(n: i32) -> Result<i32, String> {
    if n > 0 {
        Ok(n)
    } else {
        Err("not positive".into())
    }
}

fn even_r(n: i32) -> Result<i32, String> {
    if n % 2 == 0 {
        Ok(n)
    } else {
        Err("not even".into())
    }
}

// Approach 3: Dynamic pipeline from Vec of Kleisli arrows
fn pipeline(steps: &[fn(i32) -> Option<i32>], x: i32) -> Option<i32> {
    steps.iter().fold(Some(x), |acc, step| acc.and_then(step))
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_kleisli_success() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("42"), Some(21));
    }

    #[test]
    fn test_kleisli_parse_fail() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("bad"), None);
    }

    #[test]
    fn test_kleisli_not_positive() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("0"), None);
    }

    #[test]
    fn test_kleisli_not_even() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("7"), None);
    }

    #[test]
    fn test_kleisli_result_success() {
        let v = kleisli_result(kleisli_result(parse_r, positive_r), even_r);
        assert_eq!(v("42"), Ok(42));
    }

    #[test]
    fn test_kleisli_result_errors() {
        let v = kleisli_result(kleisli_result(parse_r, positive_r), even_r);
        assert_eq!(v("bad"), Err("parse failed".to_string()));
        assert_eq!(v("-1"), Err("not positive".to_string()));
        assert_eq!(v("7"), Err("not even".to_string()));
    }

    #[test]
    fn test_pipeline() {
        let steps: Vec<fn(i32) -> Option<i32>> = vec![check_positive, safe_half];
        assert_eq!(pipeline(&steps, 50), Some(25));
        assert_eq!(pipeline(&steps, -1), None);
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_kleisli_success() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("42"), Some(21));
    }

    #[test]
    fn test_kleisli_parse_fail() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("bad"), None);
    }

    #[test]
    fn test_kleisli_not_positive() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("0"), None);
    }

    #[test]
    fn test_kleisli_not_even() {
        let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
        assert_eq!(validate("7"), None);
    }

    #[test]
    fn test_kleisli_result_success() {
        let v = kleisli_result(kleisli_result(parse_r, positive_r), even_r);
        assert_eq!(v("42"), Ok(42));
    }

    #[test]
    fn test_kleisli_result_errors() {
        let v = kleisli_result(kleisli_result(parse_r, positive_r), even_r);
        assert_eq!(v("bad"), Err("parse failed".to_string()));
        assert_eq!(v("-1"), Err("not positive".to_string()));
        assert_eq!(v("7"), Err("not even".to_string()));
    }

    #[test]
    fn test_pipeline() {
        let steps: Vec<fn(i32) -> Option<i32>> = vec![check_positive, safe_half];
        assert_eq!(pipeline(&steps, 50), Some(25));
        assert_eq!(pipeline(&steps, -1), None);
    }
}

    Deep Comparison

    Comparison: Kleisli Composition

    Kleisli Operator

    OCaml:

    let ( >=> ) f g x = f x >>= g

let validate = parse_int >=> check_positive >=> safe_half
let result = validate "42"  (* Some 21 *)

    Rust:

    fn kleisli<A, B, C>(
    f: impl Fn(A) -> Option<B>,
    g: impl Fn(B) -> Option<C>,
) -> impl Fn(A) -> Option<C> {
    move |a| f(a).and_then(|b| g(b))
}

let validate = kleisli(kleisli(parse_int, check_positive), safe_half);
validate("42") // Some(21)

    Dynamic Pipeline

    OCaml:

    let pipeline steps x =
  List.fold_left (fun acc step -> acc >>= step) (Some x) steps

let steps = [check_positive; safe_half]
let result = pipeline steps 50  (* Some 25 *)

    Rust:

    fn pipeline(steps: &[fn(i32) -> Option<i32>], x: i32) -> Option<i32> {
    steps.iter().fold(Some(x), |acc, step| acc.and_then(step))
}

let steps: Vec<fn(i32) -> Option<i32>> = vec![check_positive, safe_half];
pipeline(&steps, 50) // Some(25)

    Exercises

  • Implement kleisli for Result<T, E> and chain three validation functions.
  • Verify that Kleisli composition is associative: kleisli(kleisli(f, g), h)(a) == kleisli(f, kleisli(g, h))(a).
  • Implement kleisli_id — the identity Kleisli arrow — and verify kleisli(kleisli_id, f) == f.
  • Build a middleware pipeline using Kleisli composition: each middleware transforms a request Option<Request> → Option<Response>.
  • Implement a parser combinator sequence using Kleisli composition: parse_header >=> parse_body >=> parse_footer.

    • Open Source Repos

    functional-rust

    View the source for this example on GitHub — OCaml and Rust side by side in the repo.

    Rust