Cited By
View all- Breuvart FMcDermott DUustalu T(2023)Canonical Gradings of MonadsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.380.1380(1-21)Online publication date: 7-Aug-2023
Degrading Lists
Article No.: 6, Pages 1 - 14
Abstract
We discuss the relationship between monads and their known generalisation, graded monads, which are especially useful for modelling computational effects equipped with a form of sequential composition. Specifically, we ask if a graded monad can be extended to a monad, and when such a degrading is in some sense canonical. Our particular examples are the graded monads of lists and non-empty lists indexed by their lengths, which gives us a pretext to study the space of all (non-graded) monad structures on the list and non-empty list endofunctors. We show that, in both cases, there exist infinitely many monad structures. However, while there are at least two ways to complete the graded monad structure on length-indexed lists to a monad structure on the list endofunctor, such a completion for non-empty lists is unique.
References
[1]
Michael Abbott, Thorsten Altenkirch, and Neil Ghani. 2005. Containers: Constructing Strictly Positive Types. Theoretical Computer Science 342, 1 (2005), 3–27. https://doi.org/10.1016/j.tcs.2005.06.002
[2]
Artur Barkhudaryan. 2003. Endofunctors of Set Determined by Their Object Map. Applied Categorical Structures 11, 6 (2003), 507–520. https://doi.org/10.1023/a:1026177620363
[3]
Artur Barkhudaryan, Robert El Bashir, and Věra Trnková. 2003. Endofunctors of Set and Cardinalities. Cahiers de topologie et géométrie différentielle catégoriques 44, 3 (2003), 217–239. http://www.numdam.org/item/CTGDC_2003__44_3_217_0/
[4]
Daniela Cancila, Furio Honsell, and Marina Lenisa. 2006. Functors Determined by Values on Objects. Electronic Notes in Theoretical Computer Science 158 (2006), 151–169. https://doi.org/10.1016/j.entcs.2006.04.009
[5]
Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming, ICFP ’00, Montreal, Canada, Sept. 18–21, 2000, Martin Odersky and Philip Wadler (Eds.). ACM, New York, 268–279. https://doi.org/10.1145/351240.351266
[6]
Ulrich Dorsch, Stefan Milius, and Lutz Schröder. 2019. Graded Monads and Graded Logics for the Linear Time - Branching Time Spectrum. In 30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands, Wan Fokkink and Rob van Glabbeek (Eds.). Leibniz Int. Proceedings in Informatics, Vol. 140. Dagstuhl Publishing, Saarbrücken/Wadern. https://doi.org/10.4230/lipics.concur.2019.36
[7]
Tobias Fritz and Paolo Perrone. 2018. A Criterion for Kan Extensions of Lax Monoidal Functors. arXiv eprint. arxiv:1809.10481 [math.CT]
[8]
Shin-ya Katsumata. 2014. Parametric Effect Monads and Semantics of Effect Systems. In The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’14, San Diego, CA, USA, January 20-21, 2014, Suresh Jagannathan and Peter Sewell (Eds.). ACM, New York, 633–646. https://doi.org/10.1145/2535838.2535846
[9]
Shin-ya Katsumata and Tetsuya Sato. 2013. Preorders on Monads and Coalgebraic Simulations. In Foundations of Software Science and Computation Structures - 16th International Conference, FOSSACS 2013, Rome, Italy, March 16-24, 2013. Proceedings, Frank Pfenning (Ed.). Lecture Notes in Computer Science, Vol. 7794. Springer, Cham, 145–160. https://doi.org/10.1007/978-3-642-37075-5_10
[10]
Bartek Klin and Julian Salamanca. 2018. Iterated Covariant Powerset Is Not a Monad. Electronic Notes in Theoretical Computer Science 341 (2018), 261–276. https://doi.org/10.1016/j.entcs.2018.11.013
[11]
Seerp Roald Koudenburg. 2015. Algebraic Kan Extensions in Double Categories. Theory and Applications of Categories 30, 5 (2015), 86–146. http://www.tac.mta.ca/tac/volumes/30/5/30-05abs.html
[12]
Ernie Manes. 2003. Monads of Sets. In Handbook of Algebra, Vol. 3, Michiel Hazewinkel (Ed.). Elsevier, Amsterdam, 67–153. https://doi.org/10.1016/s1570-7954(03)80059-1
[13]
Ernie Manes and Philip S. Mulry. 2008. Monad Compositions II: Kleisli Strength. Mathematical Structures in Computer Science 18, 3 (2008), 613–643. https://doi.org/10.1017/s0960129508006695
[14]
Ernest G. Manes. 1976. Algebraic Theories. Graduate Texts in Mathematics, Vol. 26. Springer, New York. https://doi.org/10.1007/978-1-4612-9860-1
[15]
Paul-André Melliès. 2017. The Parametric Continuation Monad. Mathematical Structures in Computer Science 27, 5 (2017), 651–680. https://doi.org/10.1017/S0960129515000328
[16]
Paul-André Melliès and Nicolas Tabareau. 2008. Free Models of T-Algebraic Theories Computed as Kan Extensions. HAL eprint. https://hal.archives-ouvertes.fr/hal-00339331/
[17]
Stefan Milius, Dirk Pattinson, and Lutz Schröder. 2015. Generic Trace Semantics and Graded Monads. In 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015, June 24–26, 2015, Nijmegen, The Netherlands, Lawrence S. Moss and Paweł Sobociński (Eds.). Leibniz Int. Proceedings in Informatics, Vol. 35. Dagstuhl Publishing, Saarbrücken/Wadern, 253–269. https://doi.org/10.4230/lipics.calco.2015.253
[18]
Alan Mycroft, Dominic Orchard, and Tomas Petricek. 2016. Effect Systems Revisited—Control-Flow Algebra and Semantics. In Semantics, Logics, and Calculi: Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays, Christian W. Probst, Chris Hankin, and René Rydhof Hansen (Eds.). Lecture Notes in Computer Science, Vol. 9560. Springer, Cham, 1–32. https://doi.org/10.1007/978-3-319-27810-0_1
[19]
Renato Neves. 2018. Hybrid Programs. Ph.D. Dissertation. University of Minho.
[20]
Maria Cristina Pedicchio and Fabrizio Rovatti. 2003. Algebraic Categories. In Categorical Foundations: Special Topics in Topology, Algebra, and Sheaf Theory, Maria Cristina Pedicchio and Walter Tholen (Eds.). Encyclopedia of Mathematics and Its Applications, Vol. 97. Cambridge University Press, Cambridge, 269–310. https://doi.org/10.1017/cbo9781107340985.009
[21]
Maciej Piróg, Piotr Polesiuk, and Filip Sieczkowski. 2019. Equational Theories and Monads from Polynomial Cayley Representations. In Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings, Mikołaj Bojańczyk and Alex Simpson (Eds.). Lecture Notes in Computer Science, Vol. 11425. Springer, Cham, 453–469. https://doi.org/10.1007/978-3-030-17127-8_26
[22]
Tetsuya Sato. 2014. Identifying All Preorders on the Subdistribution Monad. Electronic Notes in Theoretical Computer Science 308 (2014), 309–327. https://doi.org/10.1016/j.entcs.2014.10.017
[23]
Alexander Smirnov. 2008. Graded Monads and Rings of Polynomials. Journal of Mathematical Sciences 151 (2008), 3032–3051. https://doi.org/10.1007/s10958-008-9013-7
[24]
Tarmo Uustalu. 2017. Container Combinatorics: Monads and Lax Monoidal Functors. In Topics in Theoretical Computer Science - Second IFIP WG 1.8 International Conference, TTCS 2017, Tehran, Iran, September 12-14, 2017, Proceedings, Mohammad Reza Mousavi and Jiří Sgall (Eds.). Lecture Notes in Computer Science, Vol. 10608. Springer, Cham, 91–105. https://doi.org/10.1007/978-3-319-68953-1_8
[25]
Mark Weber. 2016. Algebraic Kan Extensions along Morphisms of Internal Algebra Classifiers. Tbilisi Mathematical Journal 9, 1 (2016), 65–142. https://doi.org/10.1515/tmj-2016-0006
[26]
Maaike Zwart and Dan Marsden. 2019. No-Go Theorems for Distributive Laws. In 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, Los Alamitos, CA, Article 8785707, 13 pages. https://doi.org/10.1109/lics.2019.8785707
Recommendations
Combining Semilattices and Semimodules
Foundations of Software Science and Computation StructuresAbstractWe describe the canonical weak distributive law of the powerset monad over the S-left-semimodule monad , for a class of semirings S. We show that the composition of with by means of such yields almost the monad of convex subsets ...
Scoped Effects as Parameterized Algebraic Theories
Programming Languages and SystemsAbstractNotions of computation can be modelled by monads. Algebraic effects offer a characterization of monads in terms of algebraic operations and equational axioms, where operations are basic programming features, such as reading or updating the state, ...
Segal Condition Meets Computational Effects
LICS '10: Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer ScienceEvery finitary monad T on the category of sets is described by an algebraic theory whose n-ary operations are the elements of the free algebra Tn generated by n letters. This canonical presentation of the monad (called its Lawvere theory)offers a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2020
179 pages
ISBN:9781450388214
DOI:10.1145/3414080
- General Chair:
- Maurizio Gabbrielli,
- Program Chairs:
- Andreas Abel,
- James Cheney
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 September 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
PPDP '20
PPDP '20: 22nd International Symposium on Principles and Practice of Declarative Programming
September 8 - 10, 2020
Bologna, Italy
Acceptance Rates
Overall Acceptance Rate 230 of 486 submissions, 47%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 71Total Downloads
- Downloads (Last 12 months)15
- Downloads (Last 6 weeks)2
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
Cited By
View all- Breuvart FMcDermott DUustalu T(2023)Canonical Gradings of MonadsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.380.1380(1-21)Online publication date: 7-Aug-2023
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format