From Monoids to NearSemirings: The Essence of MonadPlus and Alternative

with Exequiel Rivas and Tom Schrijvers. PPDP 2015.PDF

Abstract

It is well-known that monads are monoids in the category of endo- functors, and in fact so are applicative functors. Unfortunately, the benefits of this unified view are lost when the additional non-determinism structure of MonadPlus or Alternative is required.

This article recovers the essence of these two type classes by extending monoids to near-semirings with both additive and multi- plicative structure. This unified algebraic view enables us to gener- ically define the free construction as well as a novel double Cayley representation that optimises both left-nested sums and left-nested products.

BibTeX

@inproceedings{RJS:2015,
 author     = {Rivas, Exequiel and Jaskelioff, Mauro and Schrijvers, Tom},
 title      = {From Monoids to NearSemirings: The Essence of MonadPlus and Alternative},
editor      = {Moreno Falaschi and Elvira Albert},
 booktitle  = {Proceedings of the  17th International Symposium on Principles and Practice of Declarative Programming},
 url        = {http://doi.acm.org/10.1145/2790449.2790514},
 doi        = {10.1145/2790449.2790514},
 isbn       = {978-1-4503-3516-4},
 series     = {PPDP'15},
 publisher  = {{ACM}},
 year       = {2015},
 pages      = {196--207},
 location   = {Siena, Italy}
}