Title: Eilenberg-Moore monoids and backtracking monad transformers
Authors: PirĂ³g, Maciej # ×
Issue Date: 1-Apr-2016
Publisher: Open Publishing Association
Series Title: Electronic Proceedings in Theoretical Computer Science vol:207 pages:23-56
Conference: Workshop on Mathematically Structured Functional Programming edition:6 location:Eindhoven, Netherlands date:8 April 2016
Abstract: 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.
ISSN: 2075-2180
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
emmon.pdf Published 346KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science