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?

  • $\begingroup$ What do you mean by "expressed"? $\endgroup$ – Martin Berger Jan 7 '16 at 7:39
  • $\begingroup$ @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). $\endgroup$ – NietzscheanAI Jan 7 '16 at 9:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.