From Monoids to NearSemirings: The Essence of MonadPlus and Alternative

EXEQUIEL RIVAS; MAURO JASKELIOFF; TOM SCHRIJVERS

Siena

Simposio; 17th International Symposium on Principles and Practice of Declarative Programming; 2015

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.