Monads need not be endofunctors

Thosten Altenkirch; James Chapman; Tarmo Uustalu

doi:10.2168/LMCS-11(1:3)2015

Thosten Altenkirch ; James Chapman ; Tarmo Uustalu - Monads need not be endofunctors

lmcs:928 - Logical Methods in Computer Science, March 6, 2015, Volume 11, Issue 1 - https://doi.org/10.2168/LMCS-11(1:3)2015

Monads need not be endofunctorsArticle

Authors: Thosten Altenkirch ; James Chapman ; Tarmo Uustalu

We introduce a generalization of monads, called relative monads, allowing for underlying functors between different categories. Examples include finite-dimensional vector spaces, untyped and typed lambda-calculus syntax and indexed containers. We show that the Kleisli and Eilenberg-Moore constructions carry over to relative monads and are related to relative adjunctions. Under reasonable assumptions, relative monads are monoids in the functor category concerned and extend to monads, giving rise to a coreflection between relative monads and monads. Arrows are also an instance of relative monads.

https://doi.org/10.2168/LMCS-11(1:3)2015

Source: arXiv.org:1412.7148

Volume: Volume 11, Issue 1

Secondary volumes: Selected Papers of the 13th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2010)

Published on: March 6, 2015

Imported on: May 4, 2011

Keywords: Computer Science - Programming Languages, Computer Science - Logic in Computer Science, Mathematics - Category Theory

Licence: arXiv.org - Non-exclusive license to distribute

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

39 Documents citing this article

Benedikt Ahrens;Ambroise Lafont;Thomas Lamiaux, 2025, 2-Functoriality of Initial Semantics, and Applications, Proceedings of the ACM on Programming Languages, 9, ICFP, pp. 643-674, 10.1145/3747527, https://doi.org/10.1145/3747527.

Hisham Sati;Urs Schreiber, 2025, The quantum monadology, Quantum Studies Mathematics and Foundations, 12, 3, 10.1007/s40509-025-00368-5.

Jack Liell-Cock;Sam Staton, 2025, Compositional Imprecise Probability: A Solution from Graded Monads and Markov Categories, Proceedings of the ACM on Programming Languages, 9, POPL, pp. 1596-1626, 10.1145/3704890, https://doi.org/10.1145/3704890.

Nathanael Arkor;Dylan McDermott, 2025, The nerve theorem for relative monads, Theory and applications of categories, 43, pp. 403-454, 10.70930/tac/jjc9mnky, https://doi.org/10.70930/tac/jjc9mnky.

Thea Li, 2025, Fibrational Perspectives on Determinization of Finite-State Automata, Electronic Proceedings in Theoretical Computer Science, 429, pp. 203-216, 10.4204/eptcs.429.11, https://doi.org/10.4204/eptcs.429.11.

Cheng-Syuan Wan, 2024, Semi-Substructural Logics à la Lambek, Electronic Proceedings in Theoretical Computer Science, 415, pp. 195-213, 10.4204/eptcs.415.18, https://doi.org/10.4204/eptcs.415.18.

Niccolò Veltri;Cheng-Syuan Wan, 2024, Semi-Substructural Logics with Additives, Electronic Proceedings in Theoretical Computer Science, 402, pp. 63-80, 10.4204/eptcs.402.8, http://dx.doi.org/10.4204/eptcs.402.8.

Andrew Slattery, 2023, Pseudocommutativity and lax idempotency for relative pseudomonads, Theory and applications of categories, 39, pp. 1018-1049, 10.70930/tac/asekq7ut, https://doi.org/10.70930/tac/asekq7ut.

Niccolò Veltri, 2023, Maximally Multi-focused Proofs for Skew Non-Commutative MILL, Lecture notes in computer science, pp. 377-393, 10.1007/978-3-031-39784-4_24.

Philipp G. Haselwarter;Exequiel Rivas;Antoine Van Muylder;Théo Winterhalter;Carmine Abate;et al., 2023, SSProve: A Foundational Framework for Modular Cryptographic Proofs in Coq, ACM Transactions on Programming Languages and Systems, 45, 3, pp. 1-61, 10.1145/3594735, https://doi.org/10.1145/3594735.

Rory B. B. Lucyshyn-Wright;Jason Parker, 2023, Diagrammatic Presentations of Enriched Monads and Varieties for a Subcategory of Arities, Applied Categorical Structures, 31, 5, 10.1007/s10485-023-09735-y.

André Hirschowitz;Tom Hirschowitz;Ambroise Lafont;Marco Maggesi, 2022, Variable binding and substitution for (nameless) dummies, Lecture notes in computer science, pp. 389-408, 10.1007/978-3-030-99253-8_20, https://doi.org/10.1007/978-3-030-99253-8_20.

Danielle Marshall;Michael Vollmer;Dominic Orchard, 2022, Linearity and Uniqueness: An Entente Cordiale, Lecture notes in computer science, pp. 346-375, 10.1007/978-3-030-99336-8_13, https://doi.org/10.1007/978-3-030-99336-8_13.

Dylan McDermott;Tarmo Uustalu, 2022, Flexibly Graded Monads and Graded Algebras, Lecture notes in computer science, pp. 102-128, 10.1007/978-3-031-16912-0_4.

Shin-ya Katsumata;Dylan McDermott;Tarmo Uustalu;Nicolas Wu, 2022, Flexible presentations of graded monads, Proceedings of the ACM on Programming Languages, 6, ICFP, pp. 902-930, 10.1145/3547654, https://doi.org/10.1145/3547654.

Tarmo Uustalu;Niccolò Veltri;Cheng-Syuan Wan, 2022, Proof Theory of Skew Non-Commutative MILL, Electronic Proceedings in Theoretical Computer Science, 358, pp. 118-135, 10.4204/eptcs.358.9, https://doi.org/10.4204/eptcs.358.9.

Vladimir Voevodsky, 2022, C-system of a module over a Jf-relative monad, Journal of Pure and Applied Algebra, 227, 6, pp. 107283, 10.1016/j.jpaa.2022.107283.

Arjen Rouvoet;Robbert Krebbers;Eelco Visser, 2021, Intrinsically typed compilation with nameless labels, Proceedings of the ACM on Programming Languages, 5, POPL, pp. 1-28, 10.1145/3434303, https://doi.org/10.1145/3434303.

GUILLAUME ALLAIS;ROBERT ATKEY;JAMES CHAPMAN;CONOR MCBRIDE;JAMES MCKINNA, 2021, A type- and scope-safe universe of syntaxes with binding: their semantics and proofs, Journal of Functional Programming, 31, 10.1017/s0956796820000076, https://doi.org/10.1017/s0956796820000076.

Richard Garner;Jean-Simon Pacaud Lemay, 2021, Cartesian Differential Categories as Skew Enriched Categories, Applied Categorical Structures, 29, 6, pp. 1099-1150, 10.1007/s10485-021-09649-7, https://doi.org/10.1007/s10485-021-09649-7.

Arjen Rouvoet;Casper Bach Poulsen;Robbert Krebbers;Eelco Visser, 2020, Intrinsically-typed definitional interpreters for linear, session-typed languages, Data Archiving and Networked Services (DANS), pp. 284-298, 10.1145/3372885.3373818, http://resolver.tudelft.nl/uuid:913a5c7f-d521-445e-82af-a7771849f964.

Hirschowitz, André;Hirschowitz, Tom;Lafont, Ambroise, 2020, Modules over Monads and Operational Semantics, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.fscd.2020.12, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.12.

Peio Borthelle;Tom Hirschowitz;Ambroise Lafont, 2020, A Cellular Howe Theorem, pp. 273-286, 10.1145/3373718.3394738, https://hal.science/hal-02880876.

Tarmo Uustalu;Niccolò Veltri;Noam Zeilberger, 2020, Eilenberg-Kelly Reloaded, Electronic Notes in Theoretical Computer Science, 352, pp. 233-256, 10.1016/j.entcs.2020.09.012, https://doi.org/10.1016/j.entcs.2020.09.012.

ANDREAS ABEL;GUILLAUME ALLAIS;ALIYA HAMEER;BRIGITTE PIENTKA;ALBERTO MOMIGLIANO;et al., 2019, POPLMark reloaded: Mechanizing proofs by logical relations, Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano), 29, 10.1017/s0956796819000170, http://hdl.handle.net/2434/695543.

Arthur Azevedo de Amorim;Marco Gaboardi;Justin Hsu;Shin-ya Katsumata, 2019, Probabilistic Relational Reasoning via Metrics, 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-19, 10.1109/lics.2019.8785715.

Benedikt Ahrens;André Hirschowitz;Ambroise Lafont;Marco Maggesi, 2019, Reduction monads and their signatures, Proceedings of the ACM on Programming Languages, 4, POPL, pp. 1-29, 10.1145/3371099, https://doi.org/10.1145/3371099.

Härmel Nestra, 2019, Laws of Monadic Error Handling, Lecture notes in computer science, pp. 372-391, 10.1007/978-3-030-32505-3_21.

James Chapman;Roman Kireev;Chad Nester;Philip Wadler, 2019, System F in Agda, for Fun and Profit, Edinburgh Research Explorer, pp. 255-297, 10.1007/978-3-030-33636-3_10, https://www.research.ed.ac.uk/en/publications/62107dbc-a5b7-4361-a28d-7ce0635f73c8.

Kenji Maillard;Cătălin Hriţcu;Exequiel Rivas;Antoine Van Muylder, 2019, The next 700 relational program logics, Proceedings of the ACM on Programming Languages, 4, POPL, pp. 1-33, 10.1145/3371072, https://doi.org/10.1145/3371072.

Makoto Hamana;Tatsuya Abe;Kentaro Kikuchi, 2019, Polymorphic computation systems: Theory and practice of confluence with call-by-value, Science of Computer Programming, 187, pp. 102322, 10.1016/j.scico.2019.102322.

Oleg Kiselyov, 2019, Effects Without Monads: Non-determinism – Back to the Meta Language, Electronic Proceedings in Theoretical Computer Science, 294, pp. 15-40, 10.4204/eptcs.294.2, https://doi.org/10.4204/eptcs.294.2.

Dusko Pavlovic;Muzamil Yahia, 2018, Monoidal Computer III: A Coalgebraic View of Computability and Complexity (Extended Abstract), pp. 167-189, 10.1007/978-3-030-00389-0_10, https://inria.hal.science/hal-02044646.

Exequiel Rivas, 2018, Relating Idioms, Arrows and Monads from Monoidal Adjunctions, Electronic Proceedings in Theoretical Computer Science, 275, pp. 18-33, 10.4204/eptcs.275.3, https://doi.org/10.4204/eptcs.275.3.

Tarmo Uustalu;Niccolò Veltri;Noam Zeilberger, 2018, The Sequent Calculus of Skew Monoidal Categories, Electronic Notes in Theoretical Computer Science, 341, pp. 345-370, 10.1016/j.entcs.2018.11.017, https://doi.org/10.1016/j.entcs.2018.11.017.

Marcelo Fiore, 2017, On the concrete representation of discrete enriched abstract clones, Tbilisi Mathematical Journal, 10, 3, 10.1515/tmj-2017-0115, https://doi.org/10.1515/tmj-2017-0115.

Danel Ahman;Tarmo Uustalu, 2016, Directed Containers as Categories, Electronic Proceedings in Theoretical Computer Science, 207, pp. 89-98, 10.4204/eptcs.207.5, https://doi.org/10.4204/eptcs.207.5.

Rory B. B. Lucyshyn-Wright, 2016, Enriched algebraic theories and monads for a system of arities, Theory and applications of categories, 31, pp. 101-137, 10.70930/tac/uidgtsv3, https://doi.org/10.70930/tac/uidgtsv3.

Fiore, Marcelo;Mahmoud, Ola, 2014, Abstract Clones for Abstract Syntax, DROPS (Schloss Dagstuhl – Leibniz Center for Informatics), 10.4230/lipics.fscd.2021.30, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2021.30.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 4875 times.

This article's PDF has been downloaded 1228 times.