Side effects are not side effects if you make them part of the return type. A Kleisli category redefines 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.
Python
# Functions that return value + logdef to_upper(s):
return (s.upper(), "to_upper ")
def to_words(s):
return (s.split(), "to_words ")
print(f"to_upper: {to_upper('hello world')}")
print(f"to_words: {to_words('HELLO WORLD')}")
# to_words(to_upper("hello")) fails โ type mismatch
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.
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.
Every category needs an identity morphism. In the Kleisli category for Writer, identity returns the value unchanged and contributes an empty log. Identity and fish together let us check the three category laws: left identity, right identity, and associativity.
The Writer monad lets you add logging to pure functions. Each function declares what it logs in its return type. Composition handles the plumbing. No mutable state. 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.
Python
# Logging pipeline โ no mutation, no global statedef fish(f, g):
def composed(x):
val1, log1 = f(x)
val2, log2 = g(val1)
return (val2, log1 + log2)
return composed
def validate_age(n):
if0 <= n <= 150:
return (n, "validated ")
return (-1, "INVALID ")
def categorize(n):
if n < 0: return ("invalid", "categorized ")
if n < 18: return ("minor", "categorized ")
if n < 65: return ("adult", "categorized ")
return ("senior", "categorized ")
def format_result(cat):
return (f"Category: {cat}", "formatted ")
pipeline = fish(fish(validate_age, categorize), format_result)
print(pipeline(25))
print(pipeline(200))
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 recipe is the same each time: 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
๐ Fritz 2020 โ Markov categories via the distribution monad's Kleisli category. See Ambient Category for how this gives stochastic maps compositional semantics.
๐ Staton 2025 โ probabilistic programs compose via Kleisli arrows
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. Logs accumulate via list append, but the construction works for any monoid (strings, numbers under addition, etc.) and any monad, not just Writer.
Ready for the real thing? Read the blog post. Start with the C++ examples, then try the Haskell fish operator.
Ambient Category for how this gives stochastic maps compositional semantics.
Kleisli category