Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Algebraic Presentation of Semifree Monads

  • Conference paper
  • First Online:
Coalgebraic Methods in Computer Science (CMCS 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13225))

Included in the following conference series:

Abstract

Monads and their composition via distributive laws have many applications in program semantics and functional programming. For many interesting monads, distributive laws fail to exist, and this has motivated investigations into weaker notions. In this line of research, Petrişan and Sarkis recently introduced a construction called the semifree monad in order to study semialgebras for a monad and weak distributive laws. In this paper, we prove that an algebraic presentation of the semifree monad \(M^{\mathrm {s}}\) on a monad M can be obtained uniformly from an algebraic presentation of M. This result was conjectured by Petrişan and Sarkis. We also show that semifree monads are ideal monads, that the semifree construction is not a monad transformer, and that the semifree construction is a comonad on the category of monads.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aczel, P., Adámek, J., Milius, S., Velebil, J.: Infinite trees and completely iterative theories: a coalgebraic view. Theoret. Comput. Sci. 300(1–3), 1–45 (2003). https://doi.org/10.1016/S0304-3975(02)00728-4

    Article  MathSciNet  MATH  Google Scholar 

  2. Adamek, J., Rosicky, J.: Locally Presentable and Accessible Categories. London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge (1994). https://doi.org/10.1017/CBO9780511600579

  3. Adámek, J., Milius, S., Bowler, N.J., Levy, P.B.: Coproducts of monads on set. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, 25–28 June 2012, pp. 45–54. IEEE Computer Society (2012). https://doi.org/10.1109/LICS.2012.16

  4. Awodey, S.: Category Theory. Oxford Logic Guides. Ebsco Publishing (2006)

    Google Scholar 

  5. Barr, M., Wells, C.: Toposes, Triples and Theories. Comprehensive Studies in Mathematics. Springer, New York (1985)

    Google Scholar 

  6. Beck, J.: Distributive laws. In: Eckmann, B. (ed.) Seminar on Triples and Categorical Homology Theory. LNM, vol. 80, pp. 119–140. Springer, Heidelberg (1969). https://doi.org/10.1007/BFb0083084

    Chapter  Google Scholar 

  7. Bonchi, F., Santamaria, A.: Combining semilattices and semimodules. In: FOSSACS 2021. LNCS, vol. 12650, pp. 102–123. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-71995-1_6

    Chapter  MATH  Google Scholar 

  8. Bonchi, F., Sokolova, A., Vignudelli, V.: The theory of traces for systems with nondeterminism and probability. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, pp. 1–14. IEEE (2019). https://doi.org/10.1109/LICS.2019.8785673

  9. Böhm, G.: The weak theory of monads. Adv. Math. 225, 1–32 (2010). https://doi.org/10.1016/j.aim.2010.02.015

  10. Elgot, C.C., Bloom, S.L., Tindell, R.: On the algebraic structure of rooted trees. J. Comput. Syst. Sci. 16, 361–399 (1978). https://doi.org/10.1007/978-1-4613-8177-8_7

    Article  MathSciNet  MATH  Google Scholar 

  11. Garner, R.: The vietoris monad and weak distributive laws. Appl. Categ. Struct. 28(2), 339–354 (2019). https://doi.org/10.1007/s10485-019-09582-w

    Article  MathSciNet  MATH  Google Scholar 

  12. Ghani, N., Uustalu, T.: Coproducts of ideal monads. RAIRO Theor. Inform. Appl. 38(4), 321–342 (2004). https://doi.org/10.1051/ita:2004016

  13. Goy, A., Petrisan, D.: Combining probabilistic and non-deterministic choice via weak distributive laws. In: Hermanns, H., Zhang, L., Kobayashi, N., Miller, D. (eds.) LICS 2020: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 454–464. ACM (2020). https://doi.org/10.1145/3373718.3394795

  14. van Heerdt, G., Sammartino, M., Silva, A.: Learning automata with side-effects. In: Petrişan, D., Rot, J. (eds.) CMCS 2020. LNCS, vol. 12094, pp. 68–89. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57201-3_5

    Chapter  Google Scholar 

  15. Hyland, M., Plotkin, G.D., Power, J.: Combining effects: sum and tensor. Theoret. Comput. Sci. 357(1–3), 70–99 (2006). https://doi.org/10.1016/j.tcs.2006.03.013

    Article  MathSciNet  MATH  Google Scholar 

  16. Hyland, M., Tasson, C.: The linear-non-linear substitution 2-monad. In: Spivak, D.I., Vicary, J. (eds.) Proceedings of the 3rd Annual International Applied Category Theory Conference 2020, ACT 2020. EPTCS, vol. 333, pp. 215–229 (2020). https://doi.org/10.4204/EPTCS.333.15

  17. Jacobs, B.: Semantics of weakening and contraction. Ann. Pure Appl. Logic 69(1), 73–106 (1994). https://doi.org/10.1016/0168-0072(94)90020-5

    Article  MathSciNet  MATH  Google Scholar 

  18. Jacobs, B.: Convexity, duality and effects. In: Calude, C.S., Sassone, V. (eds.) TCS 2010. IAICT, vol. 323, pp. 1–19. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15240-5_1

    Chapter  Google Scholar 

  19. Jacobs, B., Silva, A., Sokolova, A.: Trace semantics via determinization. J. Comput. Syst. Sci. 81(5), 859–879 (2015). https://doi.org/10.1016/j.jcss.2014.12.005

    Article  MathSciNet  MATH  Google Scholar 

  20. Jaskelioff, M.: Modular monad transformers. In: Castagna, G. (ed.) ESOP 2009. LNCS, vol. 5502, pp. 64–79. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00590-9_6

    Chapter  Google Scholar 

  21. Katsumata, S., Rivas, E., Uustalu, T.: Interaction laws of monads and comonads. In: Hermanns, H., Zhang, L., Kobayashi, N., Miller, D. (eds.) LICS 2020: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pp. 604–618. ACM (2020). https://doi.org/10.1145/3373718.3394808

  22. Klin, B., Salamanca, J.: Iterated covariant powerset is not a monad. In: Staton, S. (ed.) Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics, MFPS 2018. Electronic Notes in Theoretical Computer Science, vol. 341, pp. 261–276. Elsevier (2018). https://doi.org/10.1016/j.entcs.2018.11.013

  23. Kupferman, O., Lustig, Y.: Lattice automata. In: Cook, B., Podelski, A. (eds.) VMCAI 2007. LNCS, vol. 4349, pp. 199–213. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-69738-1_14

    Chapter  Google Scholar 

  24. Liang, S., Hudak, P., Jones, M.P.: Monad transformers and modular interpreters. In: Cytron, R.K., Lee, P. (eds.) Conference Record of POPL 1995: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Francisco, California, USA, 23–25 January 1995, pp. 333–343. ACM Press (1995). https://doi.org/10.1145/199448.199528

  25. MacLane, S.: Categories for the Working Mathematician. Graduate Texts in Mathematics, vol. 5. Springer, New York (1971)

    MATH  Google Scholar 

  26. Manes, E.: Algebraic Theories. Graduate Texts in Mathematics, vol. 26. Springer, New York (1976). https://doi.org/10.1007/978-1-4612-9860-1

    Book  MATH  Google Scholar 

  27. Métayer, F.: State monads and their algebras. arXiv:math/0407251, Category Theory (2004). https://doi.org/10.48550/arXiv.math/0407251

  28. Milius, S., Pattinson, D., Schröder, L.: Generic trace semantics and graded monads. In: Moss, L.S., Sobocinski, P. (eds.) 6th Conference on Algebra and Coalgebra in Computer Science, CALCO 2015. LIPIcs, vol. 35, pp. 253–269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015). https://doi.org/10.4230/LIPIcs.CALCO.2015.253

  29. Mio, M., Sarkis, R., Vignudelli, V.: Combining nondeterminism, probability, and termination: equational and metric reasoning. In: 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, pp. 1–14. IEEE (2021). https://doi.org/10.1109/LICS52264.2021.9470717

  30. Mio, M., Vignudelli, V.: Monads and quantitative equational theories for nondeterminism and probability. In: Konnov, I., Kovács, L. (eds.) 31st International Conference on Concurrency Theory, CONCUR 2020. LIPIcs, vol. 171, pp. 28:1–28:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020). https://doi.org/10.4230/LIPIcs.CONCUR.2020.28

  31. Moggi, E.: Notions of computation and monads. Inf. Comput. 93(1), 55–92 (1991). https://doi.org/10.1016/0890-5401(91)90052-4. Selections from 1989 IEEE Symposium on Logic in Computer Science

  32. Petrisan, D., Sarkis, R.: Semialgebras and weak distributive laws. In: Sokolova, A. (ed.) Proceedings 37th Conference on Mathematical Foundations of Programming Semantics, MFPS 2021. EPTCS, vol. 351, pp. 218–241 (2021). https://doi.org/10.4204/EPTCS.351.14

  33. Plotkin, G.D., Power, J.: Notions of computation determine monads. In: Nielsen, M., Engberg, U. (eds.) Foundations of Software Science and Computation Structures, vol. 2303, pp. 342–356. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45931-6_247

    Chapter  MATH  Google Scholar 

  34. Power, J.: Discrete Lawvere theories. In: Fiadeiro, J.L., Harman, N., Roggenbach, M., Rutten, J. (eds.) CALCO 2005. LNCS, vol. 3629, pp. 348–363. Springer, Heidelberg (2005). https://doi.org/10.1007/11548133_22

    Chapter  Google Scholar 

  35. Riehl, E.: Category Theory in Context. Dover Modern Math Originals, Dover Publications, Aurora (2017)

    Google Scholar 

  36. Rosset, A., Hansen, H.H., Endrullis, J.: Algebraic presentation of semifree monads. arXiv:cs.LO (2022). https://doi.org/10.48550/ARXIV.2205.05392

  37. Street, R.: Weak distributive laws. Theory Appl. Categories 22, 313–320 (2009)

    Google Scholar 

  38. Varacca, D., Winskel, G.: Distributing probabililty over nondeterminism. Math. Struct. Comput. Sci. 16, 87–113 (2006). https://doi.org/10.1017/S0960129505005074

    Article  MATH  Google Scholar 

  39. Wadler, P.: The essence of functional programming. In: Sethi, R. (ed.) Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 1–14. ACM Press (1992). https://doi.org/10.1145/143165.143169

  40. Zwart, M., Marsden, D.: No-go theorems for distributive laws. In: 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, pp. 1–13. IEEE (2019). https://doi.org/10.1109/LICS.2019.8785707

Download references

Acknowledgment

We thank Ralph Sarkis, and Roy Overbeek for useful discussion, suggestions and corrections. We also thank all anonymous reviewers for their valuable feedback and suggestions. Aloïs Rosset and Jörg Endrullis received funding from the Netherlands Organization for Scientific Research (NWO) under the Innovational Research Incentives Scheme Vidi (project. No. VI.Vidi.192.004).

Author information

Authors and Affiliations

  1. Vrije Universiteit Amsterdam, Amsterdam, Netherlands

    Aloïs Rosset & Jörg Endrullis

  2. University of Groningen, Groningen, Netherlands

    Helle Hvid Hansen

Authors
  1. Aloïs Rosset
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Helle Hvid Hansen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jörg Endrullis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Aloïs Rosset .

Editor information

Editors and Affiliations

  1. University of Groningen, Groningen, The Netherlands

    Helle Hvid Hansen

  2. University College London, London, UK

    Fabio Zanasi

Rights and permissions

Reprints and permissions

Copyright information

© 2022 IFIP International Federation for Information Processing

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rosset, A., Hansen, H.H., Endrullis, J. (2022). Algebraic Presentation of Semifree Monads. In: Hansen, H.H., Zanasi, F. (eds) Coalgebraic Methods in Computer Science. CMCS 2022. Lecture Notes in Computer Science, vol 13225. Springer, Cham. https://doi.org/10.1007/978-3-031-10736-8_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-10736-8_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-10735-1

  • Online ISBN: 978-3-031-10736-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation