<p>In my understanding, algebraic data types are basically types whose terms arise as the terms freely constructed by an algebraic specification: the operations of this specification being the term-constructors.</p>

<p>From this point of view, it seems to me that the only possible structures you can represent with algebraic data types are the free ones, that is those algebraic structures where no axiom is required: for instance magmas.</p>

<p>Observe that the fact you can represent free-monoids (that is monoids of strings/lists) as algebraic data types comes from the fact that lists are  ADTs for the algebraic specification with a <span class="math-container">$0$</span>-ary operation (namely <span class="math-container">$\text{Nil}$</span> or <span class="math-container">$[]$</span>) and a binary operation (<span class="math-container">$cons$</span> or <span class="math-container">$(:)$</span>).</p>

<p>Until you work constrained in the setting of simple types you cannot add constraints (that is equations) in your data-types, hence you cannot represent more general algebraic structures.</p>

<p>A possible way to solve this problem is to use dependent type systems with an identity type: in these type-systems you can represent algebraic structures because equations(constraints) becomes terms (they are the same as programs).</p>

<p>Hope this helps.</p>

CC BY-SA 4.0
2016-01-11T12:39:24.377Z
2019-06-14T15:54:41.453Z
2019-06-14T15:54:41.453Z
Giorgio Mossa
<p>Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)?</p>

<p>Presumably a free monoid can be considered to be isomorphic to the familiar Nil, Cons construction for lists. Can finitely-presented monoids be represented as an ADT?</p>

<p>If ADTs can't model structures having inverses, then is there a generalisation which can?</p>

CC BY-SA 3.0
2016-01-07T07:39:52.873Z
What do you mean by "expressed"?
Martin Berger
CC BY-SA 3.0
2016-01-07T09:56:40.363Z
@MartinBerger - By "expressed", I mean that the structure of the ADT is necessary and sufficient to constrain instances of the ADT to obey the axioms of the algebraic structure (and e.g. any additional constraints given by a finite presentation).
NietzscheanAI
<ds.data-structures><algebra>
Algebra and algebraic data types
NietzscheanAI
# Algebra and algebraic data types

(Asked by: username_0 on 2016-01-02)

Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)?

Presumably a free monoid can be considered to be isomorphic to the familiar Nil, Cons construction for lists. Can finitely-presented monoids be represented as an ADT?

If ADTs can't model structures having inverses, then is there a generalisation which can?

**Tags:** ds.data-structures, algebra

> **Comments:**
> **username_1**: What do you mean by "expressed"?  
> **username_0**: @MartinBerger - By "expressed", I mean that the structure of the ADT is necessary and sufficient to constrain instances of the ADT to obey the axioms of the algebraic structure (and e.g. any additional constraints given by a finite presentation).  

---

## 1 answers

### Answer by username_2 on 2016-01-11. Score: 4 | Accepted answer

In my understanding, algebraic data types are basically types whose terms arise as the terms freely constructed by an algebraic specification: the operations of this specification being the term-constructors.

From this point of view, it seems to me that the only possible structures you can represent with algebraic data types are the free ones, that is those algebraic structures where no axiom is required: for instance magmas.

Observe that the fact you can represent free-monoids (that is monoids of strings/lists) as algebraic data types comes from the fact that lists are ADTs for the algebraic specification with a $0$-ary operation (namely $\text{Nil}$ or $[]$) and a binary operation ($cons$ or $(:)$).

Until you work constrained in the setting of simple types you cannot add constraints (that is equations) in your data-types, hence you cannot represent more general algebraic structures.

A possible way to solve this problem is to use dependent type systems with an identity type: in these type-systems you can represent algebraic structures because equations(constraints) becomes terms (they are the same as programs).

Hope this helps.


---

