Motivation

When I first saw Flux, which was through NgRx, I could see that it had the same algebraic structure as list data structure. Projecting such seemigly complicated architecture into much simpler one enabled me to grasp it easy and quickly. In this post I'll share this experience by explaining:

1. What is Algebra in programmer's perspective?
2. The algebra you've probably been using all the time without realizing.
3. See how easy understanding Flux becomes when you know the algebra from 2.

using the least math as possible.

Prerequisite

Mathematics: You need little mathematics just enough to know what Group is.
Flux (Optional): Not necessary but is nice to know because I'm going to take it as an example at the end.

Algebra in Programmer's perspective

Defining type T conforming to Algebra A is like asking question: "How to make a T algebraically?" and writing the answer into one function called eval. Take Group as example. Group's formal definition is:

Now ask a question to yourself. How can I make an instance of T algebraically? By the definition of Group, there are only following three ways:

• binary operator $\bullet : T^2 \rightarrow T$
• unary operator $inverse: T \rightarrow T$
• nullary operator $id: 1 \rightarrow T$

Note that I expressed identity object as nullary operator and denoted the domain as 1. Denoting domain of nullary operator as 1 is legitimate since Type is Set and Set's identification is cardinality and cardinality of domain of nullary function is 1.

The eval function of an algebra is the combination of their implementions of operators into one piecewise function.

Let's see how we can define two Group algebras Mod 5 and $\mathbb{Z}$ (Integers) by implementing their eval function.

Mod N's eval and $\mathbb{Z}$ 's eval have same signature of $T^2 + T + 1 \rightarrow T$ , beause they are both Group, but different implementation, because they are different algebras.

Mod N's eval will map $x \bullet y$ to result of $x + y$ (where + is Mod N's equivalent of addition), and $x^{-1}$ to result of $-x$ , and $\mathbb{1}$ to $\overline{0}$ whereas $\mathbb{Z}$ maps $x \bullet y$ to result of $x + y$ , and $x^{-1}$ to result of $-x$ , and $\mathbb{1}$ to $0$ .

List Algebra

Now that we have some intuition about algebras let's get into something more practical and useful. One of the algebras that programmers use all the time without awareness is something I'd like to call List E algebra. Just like Group is algebraic structure List of some type E is an algebraic structure as well. Again, let's start with the question: How can we make a List E algebraically? There are two integral constructors for List.

1. Emtpy list
2. New list with new element e added to head of an existing list

Our definition of List algebra will embody these two construction as operators.

Be aware that $e$ is a constant for cardinality of type E.

The first constructor corresponds to $id$ and the second constructor corresponds to $\bullet$ . Any algebra that is to conform to this one will have to have eval function of signature of $eT + 1$ .

We will create two algebras Sum and Len conforming to List E.

Sum evaluates $id$ to 0, and $e \bullet t$ , where e is of type E, which could be anything, and t is of Int, which is inferred from the type that $id$ evaluates to, to $1 + t$ .

Len evaluates $id$ to $0_E$ (whatever the type E's equivalent for 0) and $e \bullet t$ , where e and t are both of type E, to $e + t$ .

Somehow Sum algebra evaluates to the sum of all the elements from the list and Len algebra evaluates to the number of the elements from the list. Let's look into their implementation and find how it's happening.

Here is implementation of Len's eval piecewise function:

Here is Sum's:

They both requires two information: initial value and evaluation function of signature (E, T)->T. Wait... why is it so familiar?

class Foldable t where
    foldr :: (a -> b -> b) -> b -> t a -> b

It is fold(a.k.a reduce)! The fold was the function that gets the two information and creates a new algebra!

Flux

You may have noticed the resemblance between List and Flux especially from the part where flux requires initial App State and calls the App State evaluating function "reducer". Let's say we are defining a Flux with three dispatchers with different parameters.

This Flux algebra’s eval function’s signature will be:

Since Type is Set we can use distributive property to combine dispatchers:

It became ‘List E’ algebra! Flux was just one of ‘List E’ algebra after all.

F-Algebra

What I have explained is based on a mathematical structure called F-Algebra. For further learning material on this subject I recommend this amazing post: Category Theory for Programmers: F-Algebra