2016/04/05 by Maciej Piróg
Computer Science · #cs.PL #cs.SE
paper · pdf · doi:10.4204/eptcs.207.2
published as EPTCS 207, 2016, pp. 23-56 · In Proceedings MSFP 2016, arXiv:1604.00384
arxiv created 2016/04/05 · arxiv updated 2016/08/22
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.