Flux and List have the same algebraic structure
Tags: math, algebra, flux
Published: 2020-03-31 10:08:01

---
title: Flux and List have the same algebraic structure
published: true
description: Understand why and how to see algebraic structure in programming models and take Flux as example.
tags: math,algebra,flux
---

# 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](https://en.wikipedia.org/wiki/Group_(mathematics)) 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:

{% katex %}
\begin{aligned}    
&\text{Group } T \\\\
&\bullet : T \times T \rightarrow T \\\\
&T^{-1} : T \rightarrow T \\\\
&id : () \rightarrow T \\\\
&t_1 \bullet (t_2 \bullet t_3) = (t_1 \bullet t_2) \bullet t_3 \\\\
&T^{-1}  \bullet T = T \bullet T^{-1} \\\\
&t \bullet id() = id() \bullet t = t
\end{aligned}
{% endkatex %}

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 {% katex inline %}\bullet : T^2 \rightarrow T{% endkatex %}
- unary operator {% katex inline %}inverse: T \rightarrow T{% endkatex %}
- nullary operator {% katex inline %}id: 1 \rightarrow T{% endkatex %}

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mflup2u0x904faa1cnks.jpeg)

Let's see how we can define two Group algebras [Mod 5](https://en.wikipedia.org/wiki/Modular_arithmetic#Integers_modulo_n) and {% katex inline %}\mathbb{Z}{% endkatex %}([Integers](https://en.wikipedia.org/wiki/Group_(mathematics)#First_example:_the_integers)) by implementing their `eval` function.

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/df6yq9q6w6m37vqy6l9b.jpeg)

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

# 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.

{% katex %}
\begin{aligned}
    & \text{List E } T \\\\
    & id : \textbf{1} \rightarrow T \\\\
    & \bullet : e \times T \rightarrow T
\end{aligned}
{% endkatex %}

Be aware that {% katex inline %}e{% endkatex %} is a constant for cardinality of type E.

The first constructor corresponds to {% katex inline %}id{% endkatex %} and the second constructor corresponds to {% katex inline %}\bullet{% endkatex %}. Any algebra that is to conform to this one will have to have `eval` function of signature of {% katex inline %}eT + 1{% endkatex %}.

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

*Sum* evaluates {% katex inline %}id{% endkatex %} to 0, and {% katex inline %}e \bullet t {% endkatex %}, where e is of type E, which could be anything, and t is of Int, which is inferred from the type that {% katex inline %}id{% endkatex %} evaluates to, to {% katex inline %}1 + t{% endkatex %}.

*Len* evaluates {% katex inline %}id{% endkatex %} to {% katex inline %}0_E{% endkatex %}(whatever the type E's equivalent for 0) and {% katex inline %}e \bullet t {% endkatex %}, where e and t are both of type E, to {% katex inline %}e + t{% endkatex %}.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/5tvezhsrpkxf1tf7man1.jpeg)

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:

{% katex %}
eval_{\text{len}}(x) =
\begin{cases}
    1 + t & \text{if $x = (e, t)$} \\\\
    0 & \text{else}
\end{cases}
{% endkatex %}

Here is Sum's:

{% katex %}
eval_{\text{sum}}(x) =
\begin{cases}
    e + t & \text{if $x = (e, t)$} \\\\
    0 & \text{else}
\end{cases}
{% endkatex %}

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

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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/4q6f0nnn8idyfhucmy7k.jpeg)

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.

{% katex %}
\begin{gathered}    
\begin{aligned}
    & \text{Flux } AppState \\\\
    & initialState : \textbf{1} \rightarrow AppState \\\\
    & dispatch1 : \textbf{1} \times T \rightarrow T \\\\
    & dispatch2 : A \times T \rightarrow T \\\\
    & dispatch3 : B \times C \times T \rightarrow T \\\\
\end{aligned} \\\\
\cdot \cdot \cdot
\end{gathered}
{% endkatex %}

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

{% katex %}
eval:1 + T + aT + bcT \rightarrow T
{% endkatex %}

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

{% katex %}
eval:1 + (1 + a + bc)T \rightarrow T
{% endkatex %}

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](https://bartoszmilewski.com/2017/02/28/f-algebras/)