Reducers are Monoids on Functions

Published on February 19, 2020 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, 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:

OCaml

Typescript

Haskell

Swift

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 itself; 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 reify mutations into values.

To see this, let's first implement endofunctions:

OCaml

Typescript

Haskell

Swift

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

And then consider a Person object/record/struct

OCaml

Typescript

Haskell

Swift

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

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

OCaml

Typescript

Haskell

Swift

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:

oneYearOlder, the change, is a value that we can store, manipulate, and do with what we choose.
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:

OCaml

Typescript

Haskell

Swift

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 change. 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:

OCaml

Typescript

Haskell

Swift

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 $id$ . Thus the monoid we've been talking about this whole time is $(Endo_A, \circ, id_A)$ .

OCaml

Typescript

Haskell

Swift

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 $T$ that is "lifted" to act on functions that return $T$ . More formally, $\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:

OCaml

Typescript

Haskell

Swift

(* 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 monoid 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.

OCaml

Typescript

Haskell

Swift

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) \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:

OCaml

Typescript

Haskell

Swift

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.

OCaml

Typescript

Haskell

Swift

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 $Endo_{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.