Laboratoire d'informatique de l'École polytechnique

Talk by Tarmo Uustalu: « List monads »

Speaker: Tarmo Uustalu
Location: BBB
Date: Mon, 18 Oct 2021, 14:00-15:00

For an upcoming seminar of the proofs and algorithms pole of LIX, we are delighted to welcome Tarmo Uustalu of Reykjavik University, who will be joining us online to speak about the categorical combinatorics of list monads.

Link to the online conference

Abstract: We tend to speak of the (possibly empty) list monad and the nonempty list monad, meaning the free monoid monad and the free semigroup monad, as if those were the only monad structures on the list and nonempty list endofunctors (on Set). But they are not! It may at first seem hard to construct other list and nonempty list monads, but at a closer look it turns out that examples abound. There are infinitely many list monads with the singleton function as the unit that admit a presentation with one nullary and one binary operation, and infinitely many nonempty list monads with singleton as the unit and a presentation with one binary operation; some multiplications not only delete, but even duplicate and permute elements. There are list and nonempty list monads with singleton as the unit that have no finite presentation. There are nonempty list monads whose unit is the doubleton function. You cannot tell if a nonempty list monad presented to you as a blackbox is the free semigroup monad by testing the unit and multiplication on finitely many inputs. Etc. We are far from having classified all list monads or all nonempty list monads, but these are cool combinatorial problems.

This is joint work with Dylan McDermott and Maciej Piróg.