Kleisli Categories

Bartosz Milewski · 2014 · Category Theory for Programmers, Ch. 4

Prereqs: 🍞 Chapter 1 (Category), 🍞 Chapter 2 (Types and Functions). 7 min.

Side effects are not side effects if you make them part of the return type. A Kleisli category re-defines morphisms as functions a → m(b) and composition as the fish operator (>=>). The category laws still hold. You get purity and logging (or failure, or nondeterminism) at the same time.

The problem: composing embellished functions

You have functions that return a value plus a log string. You can't compose them with ordinary function composition because the types don't line up: a → (b, string) followed by b → (c, string) needs someone to unpack the pair and concatenate the logs. That "someone" is Kleisli composition.

Scheme

; Functions that return a value AND a log.
; Type: a -> (value . log-list)
; We can't use plain compose — the types don't match.

(define (double n)
  (cons (* n 2) (list "doubled")))

(define (add-ten n)
  (cons (+ n 10) (list "added-ten")))

(display "double: ")
(display (double 5)) (newline)
(display "add-ten: ")
(display (add-ten 20)) (newline)

; We want to compose them: number -> (number . log)
; But (add-ten (double 5)) won't work —
; add-ten expects a number, not a pair.

The Writer type and Kleisli composition

The Writer type wraps a value with a log: (value . log). Kleisli composition (>=>, the "fish operator") extracts the value from the first function's result, feeds it to the second, and concatenates the logs. This is the composition rule for morphisms in the Kleisli category.

Scheme

; Writer: (value . log-list)
; Kleisli composition (fish operator): (a -> Writer b) -> (b -> Writer c) -> (a -> Writer c)

(define (fish f g)
  (lambda (x)
    (let* ((p1 (f x))
           (p2 (g (car p1))))
      (cons (car p2)
            (append (cdr p1) (cdr p2))))))

; Our embellished functions
(define (double n)
  (cons (* n 2) (list "doubled")))

(define (add-ten n)
  (cons (+ n 10) (list "added-ten")))

; Compose them with fish
(define double-then-add (fish double add-ten))

(display "composed: ")
(display (double-then-add 5)) (newline)
; => (20 . ("doubled" "added-ten"))
; Value flows through. Logs accumulate.

Identity and the category laws

Every category needs an identity morphism. In the Kleisli category for Writer, identity returns the value unchanged and contributes an empty log. With identity and fish, we can verify the three category laws: left identity, right identity, and associativity.

Scheme

; Kleisli identity: return value unchanged, empty log
(define (writer-id x)
  (cons x '()))

; Fish operator (from above)
(define (fish f g)
  (lambda (x)
    (let* ((p1 (f x))
           (p2 (g (car p1))))
      (cons (car p2)
            (append (cdr p1) (cdr p2))))))

(define (double n)
  (cons (* n 2) (list "doubled")))

; Left identity:  fish(id, f) = f
(define left  ((fish writer-id double) 5))
(define direct (double 5))
(display "left identity:  ") (display (equal? left direct)) (newline)

; Right identity: fish(f, id) = f
(define right ((fish double writer-id) 5))
(display "right identity: ") (display (equal? right direct)) (newline)

; Associativity: fish(fish(f, g), h) = fish(f, fish(g, h))
(define (add-ten n) (cons (+ n 10) (list "added-ten")))
(define (negate n) (cons (- 0 n) (list "negated")))

(define lhs ((fish (fish double add-ten) negate) 3))
(define rhs ((fish double (fish add-ten negate)) 3))
(display "associativity:  ") (display (equal? lhs rhs)) (newline)
(display "result: ") (display lhs)
; (-16 . ("doubled" "added-ten" "negated"))

; Kleisli identity: return value unchanged, empty log
(define (writer-id x)
  (cons x '()))

; Fish operator (from above)
(define (fish f g)
  (lambda (x)
    (let* ((p1 (f x))
           (p2 (g (car p1))))
      (cons (car p2)
            (append (cdr p1) (cdr p2))))))

(define (double n)
  (cons (* n 2) (list "doubled")))

; Left identity:  fish(id, f) = f
(define left  ((fish writer-id double) 5))
(define direct (double 5))
(display "left identity:  ") (display (equal? left direct)) (newline)

; Right identity: fish(f, id) = f
(define right ((fish double writer-id) 5))
(display "right identity: ") (display (equal? right direct)) (newline)

; Associativity: fish(fish(f, g), h) = fish(f, fish(g, h))
(define (add-ten n) (cons (+ n 10) (list "added-ten")))
(define (negate n) (cons (- 0 n) (list "negated")))

(define lhs ((fish (fish double add-ten) negate) 3))
(define rhs ((fish double (fish add-ten negate)) 3))
(display "associativity:  ") (display (equal? lhs rhs)) (newline)
(display "result: ") (display lhs)
; (-16 . ("doubled" "added-ten" "negated"))

Logging as a real use case

The Writer monad lets you add logging to pure functions without mutation. Each function declares what it logs in its return type. Composition handles the plumbing. No global mutable log. No side effects. Just functions and types.

Scheme

; A pipeline of "audited" functions — each logs what it did.

(define (fish f g)
  (lambda (x)
    (let* ((p1 (f x))
           (p2 (g (car p1))))
      (cons (car p2)
            (append (cdr p1) (cdr p2))))))

(define (validate-age n)
  (if (and (>= n 0) (<= n 150))
      (cons n (list "validated"))
      (cons -1 (list "INVALID"))))

(define (categorize n)
  (cond ((< n 0)  (cons 'invalid (list "categorized")))
        ((< n 18) (cons 'minor (list "categorized")))
        ((< n 65) (cons 'adult (list "categorized")))
        (else     (cons 'senior (list "categorized")))))

(define (format-result cat)
  (cons (list 'category cat) (list "formatted")))

(define pipeline (fish (fish validate-age categorize) format-result))

(display (pipeline 25)) (newline)
; ((category adult) . ("validated" "categorized" "formatted"))
(display (pipeline 200)) (newline)
; ((category invalid) . ("INVALID" "categorized" "formatted"))
; Every step is pure. The log assembles itself through composition.

Beyond Writer: the Kleisli pattern

Writer is just one Kleisli category. Replace (value . log) with (value | nothing) and you get the Maybe/Optional monad for partial functions. Replace it with a list and you get nondeterminism. The pattern is always the same: define a type embellishment, a composition rule, and an identity. If the laws hold, you have a Kleisli category.

Scheme

; Kleisli category for partial functions (Optional/Maybe)
; Embellishment: value OR 'nothing

(define (fish-maybe f g)
  (lambda (x)
    (let ((result (f x)))
      (if (eq? result 'nothing)
          'nothing
          (g result)))))

(define (maybe-id x) x)

; Safe reciprocal: fails on zero
(define (safe-recip x)
  (if (= x 0) 'nothing (/ 1 x)))

; Safe square root: fails on negative
(define (safe-root x)
  (if (< x 0) 'nothing (sqrt x)))

; Compose: safe-root-of-reciprocal
(define safe-root-recip (fish-maybe safe-recip safe-root))

(display "1/4 then sqrt: ") (display (safe-root-recip 4)) (newline)
; 0.5
(display "1/0 then sqrt: ") (display (safe-root-recip 0)) (newline)
; nothing — failure propagates
(display "1/(-1) then sqrt: ") (display (safe-root-recip -1)) (newline)
; nothing — reciprocal is -1, sqrt fails

Notation reference

Blog / Haskell	Scheme	Meaning
Writer a = (a, String)	(cons val log)	Value paired with log
(>=>) :: (a→m b) → (b→m c) → (a→m c)	(fish f g)	Kleisli composition
return :: a → m a	(writer-id x)	Kleisli identity
Maybe a	value \| 'nothing	Optional/partial result
compose m1 m2	(fish f g)	Same as >=>

Neighbors

Milewski chapters

🍞 Chapter 1 — Category: the essence of composition
(next) Chapter 5 — Products and Coproducts
✏️ Kleisli.lean — Kleisli composition formalized in Lean
🍞 Fritz 2020 — stochastic maps form a Kleisli category
🪄 Programming Ch.13 — SICP's streams are a comonadic structure in disguise

Paper pages that use Kleisli categories

🍞 Fritz 2020 — Markov categories: Kleisli category of the distribution monad is the main example. See Ambient Category for how Fritz's framework gives stochastic maps their own compositional semantics.
🍞 Staton 2025 — probabilistic programs compose via Kleisli arrows

Foundations (Wikipedia)

Translation notes

The blog post uses C++ templates and Haskell. This page uses Scheme cons pairs as the Writer type and a plain fish function for Kleisli composition. The monoid used for logs is list append. The general construction works for any monoid (strings, numbers under addition, etc.), and for any monad, not just Writer. The Optional/Maybe example at the end shows the same pattern with a different embellishment.

Ready for the real thing? Read the blog post. Start with the C++ examples, then try the Haskell fish operator.

← Great and Small by june.kim Products and Coproducts →