Kleisli composition

A function $f : a \to m b$ for a monad $m$ is a computation with an effect: it may fail, return several results, or update state. Such functions do not compose with ordinary function composition, since the output type $m b$ is not the input type of the next function. Kleisli composition fills the gap^[3]^[5].

§ 01

Definition

Kleisli composition applies $f$ and passes its result to $g$ with bind:

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

It is the composition of the Kleisli category of the monad, whose objects are types and whose arrows from $a$ to $b$ are functions $a \to m b$ ^[1]^[4].

§ 02

The monad laws

Stated with >=>, the three monad laws say that return is a left and right identity and that composition is associative^[3]:

return > = > f = f f > = > return = f (f > = > g) > = > h = f > = > (g > = > h)

These are the category laws, which is why they are easier to remember in this form than in terms of bind. A monad is lawful exactly when its Kleisli arrows form a category.

§ 03

Example

Kleisli composition for any monad, a pipeline of partial steps in the option monad, a nondeterministic pipeline in the list monad, and a randomized check of the laws.

(* Kleisli composition for a monad given by return and bind. *)
module type MONAD = sig
  type 'a t
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end
 
module Kleisli (M : MONAD) = struct
  let ( >=> ) f g x = M.bind (f x) g
end
 
module Opt = Kleisli (struct type 'a t = 'a option let return x = Some x let bind = Option.bind end)
module Lst = Kleisli (struct type 'a t = 'a list let return x = [ x ] let bind l f = List.concat_map f l end)
 
(* Partial steps compose into a partial pipeline. *)
let parse s = int_of_string_opt (String.trim s)
let positive n = if n > 0 then Some n else None
let half n = if n mod 2 = 0 then Some (n / 2) else None
let pipeline = Opt.(parse >=> positive >=> half)
 
(* Nondeterministic steps: a knight's moves on an 8x8 board. *)
let moves (c, r) =
  List.filter (fun (c, r) -> c >= 1 && c <= 8 && r >= 1 && r <= 8)
    (List.map (fun (dc, dr) -> (c + dc, r + dr))
       [ (1, 2); (2, 1); (2, -1); (1, -2); (-1, -2); (-2, -1); (-2, 1); (-1, 2) ])
 
let in_three = Lst.(moves >=> moves >=> moves)

Running it.

" 42"  -> 21
"-8"   -> None
"7"    -> None
"x"    -> None
knight from a1: 64 paths of three moves, 22 squares, h8 reachable: false
identity and associativity hold in 10000 of 10000 random cases

In the option monad a pipeline stops at the first step that fails: "-8" parses but is not positive, and "7" is positive but odd. In the list monad each step returns all possibilities, so composing moves three times enumerates every sequence of three knight moves; h8 cannot be reached in three moves from a1, since a knight changes square colour on every move and the two corners have the same colour.

§ 04

History

Heinrich Kleisli constructed the category now named after him in 1965, showing that every monad arises from an adjunction^[1]. Moggi used monads and their Kleisli categories to model computational effects in 1989 and 1991^[2], and Wadler brought monads into functional programming^[3]. Haskell's Control.Monad provides >=> and its flipped form <=<^[5].