Symmetric List Objects

arXiv:2610.37944 · math.CT, cs.LO · Submitted 2026-10-27 · Read on arXiv

math.CT, cs.LO

Submitted: 2026-10-27

Updated: 2026-10-27

Comments: Presented at MSFP'26

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

The gist: Cons-lists are fundamental to functional programming, and are well-understood as initial algebras, and as a concrete construction of free monoids.

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.

Related papers