# From list to free group

Given natural numbers $\mathbb{N}$, we could construct integers $\mathbb{Z}$ by considering the equivalence relation on $\mathbb{N} \times \mathbb{N}$ as follows,

• $(a, b)\sim(c, d)$ if $a + d + r= b + c + r$ for some $r$

Obviously, it’s a equivalence relation from properties of commutativity. Thus we have equivalence class ${[} ( a , b ){]}$ where $a, b \in \mathbb{N}$. Then, ${[}(0, 0){]} = {[}(1, 1){]} = {[}(n , n){]}$, and $-{[}(a, b){]}={[}(b, a){]}$. This construction from a commutative monoid to abelian group is called Grothendieck group.

Consider $\mathbf{List(A)} = \mu{}F_{L}$, where $F_{L}(X) = 1 + A \times X$ for some set $A$. Let $\alpha = \langle i , \mathbf{cons} \rangle$ with $i : 1 \rightarrow X$, $\mathbf{cons}: A \times X \rightarrow X$. Let $\epsilon = i(*)$ and $x, y, z, \dots \in A$, and $xs, ys, zs, \dots \in \mathbf{List(A)}$. We also write $x$ as $\mathbf{cons}(x, \epsilon)$. We could find that $\alpha$ is a initial $F$-algebra.

Define “plus” with respect to $\mathbb{N}$ on $\mathbf{List(A)} \times \mathbf{List(A)}$ as follows,

• $\mathbf{concat}(\epsilon , ys) = ys$
• $\mathbf{concat}(\mathbf{cons}(x, xs) , ys) = \mathbf{cons}(x, \mathbf{concat}(xs, ys)){]}$

where $xs, ys \in \mathbf{List(A)}$ and $x \in A$. We will abuse the notation $+$ instead of $\mathbf{concat}$ and use $::$ as $\mathbf{cons}$. Acturally, $(\mathbf{List(A)}, + , \epsilon)$ is a monoid. Though, it’s not commutative, and we can’t apply the construction of Grothendieck group.

We could define an inverse element to extend the $\mathbf{List(A)}$. Let $xs \in \mathbf{List(A)}$, we define $xs^{r}$ as its reverse list which could be defined in functional programming like Haskell as foldl (flip (:)) []$\mathbf{last}(xs)$ as the last element of xs, $\mathbf{head}(xs)$ as the initial element of xs, $\mathbf{init}(xs)$ as the list without the initial element of xs, $\mathbf{final}$ as the list without the last element.

Finally, define elements on $\mathbf{List(A)}$ with one more field, that is, $( s , x)$ where $s = +, -$ and $x \in \mathbf{List(A)}$. We could extend the “plus” as

• $xs + ys = \mathbf{last}(xs) + \mathbf{init}(ys)$ if $\mathbf{last}(xs) = -\mathbf{head}(ys)$,
• $xs + ys = xs + ys$ otherwise. the later “plus” ignores the sign field.

However, we could show that every element $xs$ in $\mathbf{List'(A)}$ has an inverse element $- xs^{r}$ and this new type is a free group generated by elements of $\mathbf{A}$. Thus, $\mathbb{N}$ is $\mathbf{List(\top)}$, and $\mathbb{Z}$ is $\mathbf{List'(\top)}$ where $\top$ is a unit type has only one element. Note that for $xs \in \mathbf{List(\top)}$, there is no difference with $xs^{r}$.

Is there any differences between $\mathbf{List'(\top)}$ and $\mathbb{Z}$ constructed by Grothendieck group ?