Notions of Computation as Monoids

with Exequiel Rivas. JFP 2017.PDF(PDF extended version)


There are different notions of computation, the most popular being monads, applicative functors, and arrows. In this article we show that these three notions can be seen as instances of a unifying abstract concept: monoids in monoidal categories. We demonstrate that even when working at this high level of generality one can obtain useful results. In particular, we give conditions under which one can obtain free monoids and Cayley representations at the level of monoidal categories, and we show that their concretisation results in useful constructions for monads, applicative functors, and arrows. Moreover, by taking advantage of the uniform presentation of the three notions of computation, we introduce a principled approach to the analysis of the relation between them.


  author    = "Rivas, Exequiel Jaskelioff, Mauro",
  year      = "2017",
  journal   = {Journal of Functional Programming},
  title     = "Notions of Computation as Monoids",
  note      = "Accepted for publication"