ICE-TCS seminar: Maciej Piróg, University of Wrocław
Equational Theories and Monads from Polynomial Cayley Representations
ICE-TCS seminar #346
Notice the unusual day and time.
Date and time: Friday, 29 November 2019, 12:40-13:25
Location: Room M104
Speaker: Maciej Piróg, University of Wrocław http://www.ii.uni.wroc.pl/~mpirog/
Title: Equational Theories and Monads from Polynomial Cayley Representations
Abstract: We generalise Cayley's theorem for monoids by providing an explicit formula for a (multi-sorted) equational theory represented by the type PX -> X, where P is an arbitrary polynomial functor with natural coefficients. From the computational perspective, examples of effects given by such theories include backtracking nondeterminism (obtained with the original Cayley representation X -> X), finite mutable state (obtained with n -> X, for a constant n), and their different combinations (via n*X -> X or X^n -> X). Moreover, we show that monads induced by such theories are implementable using the type formers available in programming languages based on a polymorphic lambda-calculus, both as compositions of algebraic datatypes and as continuation-like monads. We give a set-theoretic model of the latter in terms of Barr-dinatural transformations. We also introduce CayMon, a tool that takes a polynomial as an input and generates the corresponding equational theory together with the two implementations of the induced monad in Haskell.
This is joint work with Piotr Polesiuk and Filip Sieczkowski.
