No-Go Theorems for Distributive Laws

Add to your list(s) Download to your calendar using vCal

• Maaike Zwart (University of Oxford)
• Tuesday 23 October 2018, 14:15-15:15
• MR4, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Tamara von Glehn.

Beck’s distributive laws provide sufficient conditions under which two monads can be composed, and monads arising from distributive laws have many desirable theoretical properties. Unfortunately, finding and verifying distributive laws, or establishing if one even exists, can be extremely difficult and error-prone.

In this talk I will describe two general-purpose techniques for showing when there can be no distributive law between two monads. The first widely generalizes ideas from a counterexample attributed to Plotkin, yielding general-purpose theorems that recover the known situations in which no distributive law can exist. The second approach is entirely novel, encompassing practical situations beyond the generalisation of Plotkin’s argument, including a negative answer to the open question of whether the list monad distributes over itself. As an illustration of our no-go theorems, I will give an overview of the (im)possibility of distributive laws between members of an extension of the Boom hierarchy; a hierarchy of datatypes well-known to functional programmers.

The work I present is done in collaboration with Dan Marsden. To establish our theorems, we used an algebraic perspective on monads, exploiting a syntactic characterization of distributive laws. This approach is key to generalizing beyond what has been achieved by direct calculations in previous work.

This talk is part of the Category Theory Seminar series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Category Theory Seminar
• DPMMS Lists
• DPMMS Pure Maths Seminar
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences
• School of Physical Sciences
• bld31
• ndb35's list
• yk373's list

Note that ex-directory lists are not shown.