Eilenberg--Moore Monoids and Backtracking Monad Transformers
This work addresses foundational issues in functional programming and category theory, offering incremental theoretical insights for developers and researchers in these fields.
The paper tackles the problem of providing an algebraic foundation for backtracking monad transformers in monoidal categories by introducing Eilenberg--Moore monoids, and shows that these coincide with algebras for the list monad transformer, proving it is a monad, transformer, and MonadPlus instance.
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.