ICE-TCS seminar: Maciej Piróg, University of Wrocław

Equational Theories and Monads from Polynomial Cayley Representations

  • 29.11.2019, 12:40 - 13:25


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

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.

Vinsamlegast athugið að á viðburðum Háskólans í Reykjavík (HR) eru teknar ljósmyndir og myndbönd sem notuð eru í markaðsstarfi HR. Hægt er að nálgast frekari upplýsingar á eða með því að senda tölvupóst á netfangið:
Please note that at events hosted at Reykjavik University (RU), photographs and videos are taken which might be used for RU marketing purposes. Read more about this on our or send an e-mail: