Symmetric list objects enable free commutative monoid constructions

Symmetric List Objects

Logic in Computer Science

Summary

Lists are basic structures in programming that can be put together in order, like words in a sentence. The researchers looked at a special kind of list where the first two items can be swapped, not just kept in order. They found this lets you build something called a free commutative monoid, which is a way to combine things where order does not matter. This helps in understanding how certain mathematical and computational objects can be formed.

What this means in practice

  • For functional programming developers: Design data structures and recursion schemes where element ordering can flexibly allow commutativity, improving modularity in codebases.
  • For mathematical software engineers: Implement algebraic structures and symbolic computation systems that need free commutative monoids constructed internally within symmetric monoidal categories.

A theory result. No direct application yet.

Authors

Fiona Blackett, Vikraman Choudhury, Rin Liu

Abstract

Cons-lists are fundamental to functional programming, and are well-understood as initial algebras, and as a concrete construction of free monoids. In category theory, such list objects can be axiomatised internal to any monoidal category, with nil and cons maps, and a recursion mechanism. When strengthened to support parametrised recursion, they can be shown to give the free monoid construction. We study a small variant on parametrised list objects called parametrised symmetric list objects, in a symmetric monoidal category, where the two frontmost elements are allowed to be permuted. We show that this gives a construction of free commutative monoids, and develop some related theory.