{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T18:41:08Z","timestamp":1757616068695,"version":"3.44.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030171261"},{"type":"electronic","value":"9783030171278"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T00:00:00Z","timestamp":1554422400000},"content-version":"vor","delay-in-days":94,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We generalise Cayley\u2019s theorem for monoids by providing an explicit formula for a (multi-sorted) equational theory represented by the type <jats:inline-formula>\n              <jats:tex-math>$$PX \\rightarrow X$$<\/jats:tex-math>\n            <\/jats:inline-formula>, where <jats:inline-formula>\n              <jats:tex-math>$$P$$<\/jats:tex-math>\n            <\/jats:inline-formula> is an arbitrary polynomial endofunctor with natural coefficients. From the computational perspective, examples of effects given by such theories include backtracking nondeterminism (obtained with the original Cayley representation <jats:inline-formula>\n              <jats:tex-math>$$X \\rightarrow X$$<\/jats:tex-math>\n            <\/jats:inline-formula>), finite mutable state (obtained with <jats:inline-formula>\n              <jats:tex-math>$$n \\rightarrow X$$<\/jats:tex-math>\n            <\/jats:inline-formula>, for a constant <jats:italic>n<\/jats:italic>), and their different combinations (via <jats:inline-formula>\n              <jats:tex-math>$$n \\times X \\rightarrow X$$<\/jats:tex-math>\n            <\/jats:inline-formula> or <jats:inline-formula>\n              <jats:tex-math>$$X^n \\rightarrow X$$<\/jats:tex-math>\n            <\/jats:inline-formula>). Moreover, we show that monads induced by such theories are implementable using the type formers available in programming languages based on a polymorphic <jats:inline-formula>\n              <jats:tex-math>$$\\lambda $$<\/jats:tex-math>\n            <\/jats:inline-formula>-calculus, both as compositions of algebraic datatypes and as continuation-like monads. We give a set-theoretic model of the latter in terms of Barr-dinatural transformations. We also introduce , a tool that takes a polynomial as an input and generates the corresponding equational theory together with the two implementations of the induced monad in Haskell.<\/jats:p>","DOI":"10.1007\/978-3-030-17127-8_26","type":"book-chapter","created":{"date-parts":[[2019,4,5]],"date-time":"2019-04-05T11:11:46Z","timestamp":1554462706000},"page":"453-469","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Equational Theories and Monads from Polynomial Cayley Representations"],"prefix":"10.1007","author":[{"given":"Maciej","family":"Pir\u00f3g","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Polesiuk","sequence":"additional","affiliation":[]},{"given":"Filip","family":"Sieczkowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,5]]},"reference":[{"issue":"6","key":"26_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1017\/S0956796806006058","volume":"16","author":"R Bird","year":"2006","unstructured":"Bird, R.: Functional pearl: a program to solve Sudoku. J. Funct. Program. 16(6), 671\u2013679 (2006). http:\/\/dx.doi.org\/10.1017\/S0956796806006058","journal-title":"J. Funct. Program."},{"issue":"9","key":"26_CR2","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1080\/00029890.1990.11995668","volume":"97","author":"SL Bloom","year":"1990","unstructured":"Bloom, S.L., \u00c9sik, Z., Manes, E.G.: A Cayley theorem for Boolean algebras. Am. Math. Monthly 97(9), 831\u2013833 (1990). http:\/\/dx.doi.org\/10.2307\/2324751","journal-title":"Am. Math. Monthly"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1007\/BFb0060443","volume-title":"Reports of the Midwest Category Seminar IV","author":"E Dubuc","year":"1970","unstructured":"Dubuc, E., Street, R.: Dinatural transformations. In: MacLane, S., et al. (eds.) Reports of the Midwest Category Seminar IV, pp. 126\u2013137. Springer, Heidelberg (1970). https:\/\/doi.org\/10.1007\/BFb0060443"},{"issue":"3","key":"26_CR4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1215\/ijm\/1256068141","volume":"9","author":"S Eilenberg","year":"1965","unstructured":"Eilenberg, S., Moore, J.C.: Adjoint functors and triples. Illinois J. Math. 9(3), 381\u2013398 (1965). https:\/\/projecteuclid.org:443\/euclid.ijm\/1256068141","journal-title":"Illinois J. Math."},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1142\/S0218196798000156","volume":"8","author":"Z \u00c9sik","year":"1998","unstructured":"\u00c9sik, Z.: A Cayley theorem for ternary algebras. Int. J. Algebra Comput. 8, 311\u2013316 (1998)","journal-title":"Int. J. Algebra Comput."},{"issue":"4","key":"26_CR6","first-page":"321","volume":"38","author":"N Ghani","year":"2004","unstructured":"Ghani, N., Uustalu, T.: Coproducts of ideal monads. ITA 38(4), 321\u2013342 (2004). https:\/\/doi.org\/10.1051\/ita:2004016","journal-title":"ITA"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Gibbons, J., Hinze, R.: Just do it: simple monadic equational reasoning. In: Chakravarty, M.M.T., Hu, Z., Danvy, O. (eds.) Proceeding of the 16th ACM SIGPLAN international conference on Functional Programming, ICFP 2011, Tokyo, Japan, 19\u201321 September 2011, pp. 2\u201314. ACM (2011). http:\/\/doi.acm.org\/10.1145\/2034773.2034777","DOI":"10.1145\/2034773.2034777"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-31113-0_16","volume-title":"Mathematics of Program Construction","author":"R Hinze","year":"2012","unstructured":"Hinze, R.: Kan extensions for program optimisation Or: Art and Dan explain an old trick. In: Gibbons, J., Nogueira, P. (eds.) MPC 2012. LNCS, vol. 7342, pp. 324\u2013362. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31113-0_16"},{"issue":"1\u20133","key":"26_CR9","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2006.03.013","volume":"357","author":"M Hyland","year":"2006","unstructured":"Hyland, M., Plotkin, G.D., Power, J.: Combining effects: sum and tensor. Theor. Comput. Sci. 357(1\u20133), 70\u201399 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.03.013","journal-title":"Theor. Comput. Sci."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.entcs.2007.02.019","volume":"172","author":"M Hyland","year":"2007","unstructured":"Hyland, M., Power, J.: The category theoretic understanding of universal algebra: Lawvere theories and monads. Electron. Notes Theor. Comput. Sci. 172, 437\u2013458 (2007). https:\/\/doi.org\/10.1016\/j.entcs.2007.02.019","journal-title":"Electron. Notes Theor. Comput. Sci."},{"issue":"51\u201352","key":"26_CR11","doi-asserted-by":"publisher","first-page":"4441","DOI":"10.1016\/j.tcs.2010.09.011","volume":"411","author":"M Jaskelioff","year":"2010","unstructured":"Jaskelioff, M., Moggi, E.: Monad transformers as monoid transformers. Theor. Comput. Sci. 411(51\u201352), 4441\u20134466 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.09.011","journal-title":"Theor. Comput. Sci."},{"key":"26_CR12","unstructured":"Kock, A.: Continuous Yoneda representation of a small category (1966). Aarhus University preprint. http:\/\/home.math.au.dk\/kock\/CYRSC.pdf"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-99902-4_3","volume-title":"Proceedings of the Conference on Categorical Algebra","author":"F Linton","year":"1966","unstructured":"Linton, F.: Some aspects of equational categories. In: Eilenberg, S., Harrison, D.K., MacLane, S., R\u00f6hrl, H. (eds.) Proceedings of the Conference on Categorical Algebra, pp. 84\u201394. Springer, Heidelberg (1966). https:\/\/doi.org\/10.1007\/978-3-642-99902-4_3"},{"issue":"1","key":"26_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/0890-5401(91)90052-4","volume":"93","author":"E Moggi","year":"1991","unstructured":"Moggi, E.: Notions of computation and monads. Inf. Comput. 93(1), 55\u201392 (1991). https:\/\/doi.org\/10.1016\/0890-5401(91)90052-4","journal-title":"Inf. Comput."},{"key":"26_CR15","series-title":"London Mathematical Society Lecture Note Series","first-page":"202","volume-title":"Strong monads, algebras and fixed points","author":"PS Mulry","year":"1992","unstructured":"Mulry, P.S.: Strong monads, algebras and fixed points. London Mathematical Society Lecture Note Series, pp. 202\u2013216. Cambridge University Press, New York (1992)"},{"issue":"1","key":"26_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0022-4049(97)00036-4","volume":"128","author":"R Par\u00e9","year":"1998","unstructured":"Par\u00e9, R., Rom\u00e1n, L.: Dinatural numbers. J. Pure Appl. Algebra 128(1), 33\u201392 (1998). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022404997000364","journal-title":"J. Pure Appl. Algebra"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Pir\u00f3g, M.: Eilenberg-Moore monoids and backtracking monad transformers. In: Atkey, R., Krishnaswami, N.R. (eds.) Proceedings of 6th Workshop on Mathematically Structured Functional Programming, MSFP@ETAPS 2016, Eindhoven, Netherlands, 8th April 2016. EPTCS, vol. 207, pp. 23\u201356 (2016). https:\/\/doi.org\/10.4204\/EPTCS.207.2","DOI":"10.4204\/EPTCS.207.2"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Pir\u00f3g, M., Schrijvers, T., Wu, N., Jaskelioff, M.: Syntax and semantics for operations with scopes. In: Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science. LICS 2018, pp. 809\u2013818. ACM, New York (2018). http:\/\/doi.acm.org\/10.1145\/3209108.3209166","DOI":"10.1145\/3209108.3209166"},{"key":"26_CR19","doi-asserted-by":"publisher","first-page":"e17","DOI":"10.1017\/S0956796817000077","volume":"27","author":"M Pir\u00f3g","year":"2017","unstructured":"Pir\u00f3g, M., Staton, S.: Backtracking with cut via a distributive law and left-zero monoids. J. Funct. Program. 27, e17 (2017). https:\/\/doi.org\/10.1017\/S0956796817000077","journal-title":"J. Funct. Program."},{"key":"26_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/11548133_3","volume-title":"Algebra and Coalgebra in Computer Science","author":"G Plotkin","year":"2005","unstructured":"Plotkin, G.: Adequacy for algebraic effects with state. In: Fiadeiro, J.L., Harman, N., Roggenbach, M., Rutten, J. (eds.) CALCO 2005. LNCS, vol. 3629, pp. 51\u201351. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11548133_3"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45315-6_1","volume-title":"Foundations of Software Science and Computation Structures","author":"G Plotkin","year":"2001","unstructured":"Plotkin, G., Power, J.: Adequacy for algebraic effects. In: Honsell, F., Miculan, M. (eds.) FoSSaCS 2001. LNCS, vol. 2030, pp. 1\u201324. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45315-6_1"},{"key":"26_CR22","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/S1571-0661(04)80970-8","volume":"45","author":"GD Plotkin","year":"2001","unstructured":"Plotkin, G.D., Power, J.: Semantics for algebraic operations. Electron. Notes Theor. Comput. Sci. 45, 332\u2013345 (2001). https:\/\/doi.org\/10.1016\/S1571-0661(04)80970-8","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"26_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-45931-6_24","volume-title":"Foundations of Software Science and Computation Structures","author":"G Plotkin","year":"2002","unstructured":"Plotkin, G., Power, J.: Notions of computation determine monads. In: Nielsen, M., Engberg, U. (eds.) FoSSaCS 2002. LNCS, vol. 2303, pp. 342\u2013356. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45931-6_24"},{"key":"26_CR24","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.entcs.2004.08.008","volume":"73","author":"GD Plotkin","year":"2004","unstructured":"Plotkin, G.D., Power, J.: Computational effects and operations: an overview. Electron. Notes Theor. Comput. Sci. 73, 149\u2013163 (2004). http:\/\/dx.doi.org\/10.1016\/j.entcs.2004.08.008","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Rivas, E., Jaskelioff, M., Schrijvers, T.: From monoids to near-semirings: the essence of MonadPlus and alternative. In: Falaschi, M., Albert, E. (eds.) Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming, Siena, Italy, 14\u201316 July 2015. pp. 196\u2013207. ACM (2015). http:\/\/doi.acm.org\/10.1145\/2790449.2790514","DOI":"10.1145\/2790449.2790514"},{"key":"26_CR26","first-page":"89","volume":"104","author":"A Tarlecki","year":"2011","unstructured":"Tarlecki, A.: Some nuances of many-sorted universal algebra: a review. Bull. EATCS 104, 89\u2013111 (2011)","journal-title":"Bull. EATCS"},{"key":"26_CR27","unstructured":"Vene, V., Ghani, N., Johann, P., Uustalu, T.: Parametricity and strong dinaturality (2006). https:\/\/www.ioc.ee\/~tarmo\/tday-voore\/vene-slides.pdf"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-17127-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,5]],"date-time":"2025-09-05T17:23:47Z","timestamp":1757093027000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-17127-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030171261","9783030171278"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-17127-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"5 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Prague","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Czech Republic","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2019\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}