Reducers are Monoids on Functions

Reducers a tool for handling state changes help engineers manage complexity in their applications. In this post, we'll dig into how these reducers tick by exploring some monoids on functions, learning some formal terms, and discovering the underlying reason that many engineers reach for reducers to simplify mutations of state. All code examples will be presented in OCaml, ReasonML, TypeScript, Haskell, and Swift.

Preliminaries

I expect readers to be familiar with the material covered in the first post on semigroups and monoids, but to keep this post more or less self-contained I'll review the declaration of semigroups and monoids here:

module type Semigroup = sig
type t
(* We don't use <> in the ML langs because <> is traditionally "is not equal" *)
val (+) : t -> t -> t
end
module type Monoid = sig
include Semigroup
val empty : t
end

Endofunctions are monoids

Endofunctions, or in source code, Endo, are functions from some type to itself1; for example int -> int or Person -> Person. Endofunctions come up in everyday programming as a mechanism for somewhat paradoxicly describing mutations to data immutably. In other words, we can reify2 mutations into values.

To see this, let's first implement endofunctions:

module Endo (A: sig type t end) = struct
type t = A.t -> A.t
end

And then consider a Person object/record/struct

module Person = struct
type t =
{ name: string
; age: int
}
end

A person, Fred, can age one year like so:

module PersonEndo = Endo(struct type t = Person.t end)
let oneYearOlder : PersonEndo.t = fun p -> { p with age = p.age + 1 }
let agedFred =
let fred = { Person.name = "Fred"; age = 20 } in
let fred' = oneYearOlder fred in
fred' (* { name = "Fred", age = 21 } *)

Notice a few interesting facts here:

  1. oneYearOlder, the change, is a value that we can store, manipulate, and do with what we choose.
  2. We were able to change fred despite fred being an immutable value in our language. To do this we can introduce a new value with the changes applied.

The Semigroup

The semigroup instance on endofunctions gives us a way to combine two changes into a single change. Concretely, we may want to also change our name field to add a last name, for example, we want to addLastNameSmith:

let oneYearOlder : PersonEndo.t = fun p -> { p with age = p.age + 1 }
let addLastNameSmith : PersonEndo.t = fun p -> { p with name = p.name ^ " Smith" }
let agedFred =
let fred = { Person.name = "Fred", age = 20 } in
let change = PersonEndo.(oneYearOlder + addLastNameSmith) in
let fred' = change fred in
fred' (* { name = "Fred Smith", age = 21 } *)

The Monoid

The monoid instance provides a way to model a trivial change3. With this addition, we now have a nice base case if we're building up an arbitrary amount of changes based on some runtime information:

let change = PersonEndo.empty in
(* ... *)
let change =
change +
(if aYearPasses then
oneYearOlder
else
PersonEndo.empty)
in
()
(* etc *)

We can further improve on the above by utilizing a writer monad as described in an older post to remove all of the boilerplate doing something like the above.

The Instance

An astute reader may notice "combining changes" is function composition or \circ, and the trivial change is the identity function or idid. Thus the monoid we've been talking about this whole time is (EndoA,,idA)(Endo_A, \circ, id_A)4.

module Endo (A: sig type t end) = struct
type t = A.t -> A.t
let (+) f g = fun a -> f (g a)
let empty = ident
end

Pointwise operations over monoids are monoids

A pointwise operation is some operation \oplus on some type TT that is "lifted" to act on functions that return TT. More formally, f,g.(fg)(x)=xf(x)g(x)\forall f,g. (f \oplus g)(x) = x \rightarrow f(x) \oplus g(x). If code is your thing, what follows is the function that lifts a binary operation pointwise:

(* val liftPointwise :
( 'a -> 'a -> 'a) ->
(('x -> 'a) -> ('x -> 'a) -> ('x -> 'a)) *)
let liftPointwise op = fun f1 f2 -> fun x ->
op (f1 x) (f2 x)

An interesting property of pointwise operations is that if the underlying operation is a monoid5 then the resulting pointwise operation is a monoid too! I think a nice proof of this is to show the source code that performs this operation for us.

module LiftPointwise(M: Monoid) = struct
type 'x t = 'x -> M.t
let (+) f1 f2 = fun x -> M.((f1 x) + (f2 x))
let empty = fun _x -> M.empty
end

Sometimes you want to manipulate functions over the operations rather than the underlying operations themselves. The nice thing is we don't have to give up our monoidal superpowers when we do so!

Reducers

Manipulation of state in large applications quickly gets hairy. As an application grows, it becomes a real challenge to be sure that state mutations affect only the components you want it to. One mitigation is to centralize all of your state manipulation as best as you can ideally to one function or one file or one module. To do so, we can decouple an intention to change state (or an action) from the actual state change itself.

Reducers are one way to cleanly declare atomic chunks of state manipulation in response to these actions. Smaller reducers can be composed into bigger ones as our application's state management grows in scope.

Let's take Redux reducers as an example to explore further. According to the official documentation, a reducer is defined by a function from the previous state and an action into a new state (S,A)S(S, A) \rightarrow S. In theory, we would feed some library a bunch of these reducers and in our application we could fire actions to trigger these state changes. In code, this definition of a reducer looks as follows:

let reducer : 'state * 'action -> 'state = ()

In Redux, reducers can be combined with a combineReducers function, but it's not immediately obvious exactly how this function would work.

Reducers are monoids

Redux is great because it introduced the concept of reducers to the masses. But instead of using a library directly, let's re-arrange Redux's reducer function a bit to see if we can build the library ourselves.

let reducer : 'state * 'action -> 'state = ()
(* flip the tuple *)
let reducer : 'action * 'state -> 'state = ()
(* curry the function (unroll the tuple into a function) *)
let reducer : 'action -> 'state -> 'state = ()
(* rewrite ('state -> 'state) to StateEndo *)
let reducer : 'action -> StateEndo.t = ()
(* reducer is a monoid because StateEndo is a
monoid, and it's a pointwise function into
a monoid. *)

And we have a monoid! You could say a reducer is just the EndostateEndo_{state} monoid lifted pointwise over actions. The monoid is precisely why using reducers is a nice way to decompose and reason about state changes in your application: Breaking down problems into pieces makes them more manageable, and the identity and associativity of the monoid means gluing them back together is easy. In fact, with our monoid instance on the manipulated reducer the ϵ\epsilon and \oplus give us a Redux-like library for free.

Conclusion

Endofunctions are monoids, pointwise monoidal operations are monoids, and combining these two function-monoids give us reducers! The monoidal formulation of reducers obsoletes a need for a library to provide us a way to combine reducers and give us motivation for why reducers are such a nice way to manage changes to a larger application state.

Thank you Thomas Visser and Stephen Celis for pointing out some mistakes in early versions of this post! Thank you Janne Siera for adding F# examples to the post!

Bonus: Stick it in a Writer Monad

Reducers show up in two separate places in the comonadic UI framework implementation that I used in barbq. In comonadic UI components, one of the kinds of reducers is located inside a writer monad. Most of the time a component won't need to react to any actions, and if this is the case, components are unencumbered by boilerplate specifying a "dummy" reducer. The writer monad just takes empty for us. When we need to react to actions here, we can tell our component how to react to each one. We're able to get this nice API for free precisely because reducers are monoids.


  1. Endo means precisely that the domain and range (of a function) are the same.
  2. To reify is to make the abstract concrete, in this case, it's referring to making a "change" a value we can manipulate instead of just an operation we perform in our programs.
  3. A change that doesn't change anything
  4. The subscript A_A here is noting that there is a monoid instance for all choices of AA.
  5. Moreover, operations lifted pointwise over any algebraic structure are also members of the same algebraic structure (so this is also true for semigroups, and other structures like rings, and semilattices too).