Eilenberg–Moore Monoids and Backtracking Monad Transformers

Maciej Piróg
(Department of Computer Science, KU Leuven, Belgium)

We develop an algebraic underpinning of backtracking monad transformers in the general setting of monoidal categories. As our main technical device, we introduce Eilenberg–Moore monoids, which combine monoids with algebras for strong monads. We show that Eilenberg–Moore monoids coincide with algebras for the list monad transformer ('done right') known from Haskell libraries. From this, we obtain a number of results, including the facts that the list monad transformer is indeed a monad, a transformer, and an instance of the MonadPlus class. Finally, we construct an Eilenberg–Moore monoid of endomorphisms, which, via the codensity monad construction, yields a continuation-based implementation a la Hinze.

In Robert Atkey and Neelakantan Krishnaswami: Proceedings 6th Workshop on Mathematically Structured Functional Programming (MSFP 2016), Eindhoven, Netherlands, 8th April 2016, Electronic Proceedings in Theoretical Computer Science 207, pp. 23–56.
Published: 1st April 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.207.2 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org