Algebraic Presentation of Semifree Monads

Aloïs Rosset; Helle Hvid Hansen; Jörg Endrullis

doi:10.1007/978-3-031-10736-8_6

Algebraic Presentation of Semifree Monads

Aloïs Rosset^*, Helle Hvid Hansen, Jörg Endrullis

^*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

40 Downloads (Pure)

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^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.

Original language	English
Title of host publication	Coalgebraic Methods in Computer Science
Subtitle of host publication	16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings
Editors	Helle Hvid Hansen, Fabio Zanasi
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	110-132
Number of pages	23
ISBN (Electronic)	9783031107368
ISBN (Print)	9783031107351
DOIs	https://doi.org/10.1007/978-3-031-10736-8_6
Publication status	Published - 2022
Event	16th IFIP WG 1.3 International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with European Joint Conference on Theory and Practice of Software, ETAPS 2022 - Munich, Germany Duration: 2 Apr 2022 → 3 Apr 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13225 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th IFIP WG 1.3 International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with European Joint Conference on Theory and Practice of Software, ETAPS 2022
Country/Territory	Germany
City	Munich
Period	2/04/22 → 3/04/22

Bibliographical note

Funding Information:
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).

Publisher Copyright:
© 2022, IFIP International Federation for Information Processing.

Keywords

algebraic presentation
algebraic theory
monad
semifree

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/978-3-031-10736-8_6

Algebraic Presentation of Semifree MonadsFinal published version, 453 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Copy link address

Cite this

Rosset, A., Hansen, H. H., & Endrullis, J. (2022). Algebraic Presentation of Semifree Monads. In H. H. Hansen, & F. Zanasi (Eds.), Coalgebraic Methods in Computer Science: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings (pp. 110-132). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13225 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-10736-8_6

Rosset, Aloïs ; Hansen, Helle Hvid ; Endrullis, Jörg. / Algebraic Presentation of Semifree Monads. Coalgebraic Methods in Computer Science: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings. editor / Helle Hvid Hansen ; Fabio Zanasi. Springer Science and Business Media Deutschland GmbH, 2022. pp. 110-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{cc43d6ecd58d45bdb41012ba92770a6a,

title = "Algebraic Presentation of Semifree Monads",

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{\c s}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 Ms on a monad M can be obtained uniformly from an algebraic presentation of M. This result was conjectured by Petri{\c s}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.",

keywords = "algebraic presentation, algebraic theory, monad, semifree",

author = "Alo{\"i}s Rosset and Hansen, {Helle Hvid} and J{\"o}rg Endrullis",

note = "Funding Information: 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{\"i}s Rosset and J{\"o}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). Publisher Copyright: {\textcopyright} 2022, IFIP International Federation for Information Processing.; 16th IFIP WG 1.3 International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with European Joint Conference on Theory and Practice of Software, ETAPS 2022 ; Conference date: 02-04-2022 Through 03-04-2022",

year = "2022",

doi = "10.1007/978-3-031-10736-8_6",

language = "English",

isbn = "9783031107351",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "110--132",

editor = "Hansen, {Helle Hvid} and Fabio Zanasi",

booktitle = "Coalgebraic Methods in Computer Science",

address = "Germany",

}

Rosset, A, Hansen, HH & Endrullis, J 2022, Algebraic Presentation of Semifree Monads. in HH Hansen & F Zanasi (eds), Coalgebraic Methods in Computer Science: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13225 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 110-132, 16th IFIP WG 1.3 International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with European Joint Conference on Theory and Practice of Software, ETAPS 2022, Munich, Germany, 2/04/22. https://doi.org/10.1007/978-3-031-10736-8_6

Algebraic Presentation of Semifree Monads. / Rosset, Aloïs; Hansen, Helle Hvid; Endrullis, Jörg.
Coalgebraic Methods in Computer Science: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings. ed. / Helle Hvid Hansen; Fabio Zanasi. Springer Science and Business Media Deutschland GmbH, 2022. p. 110-132 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13225 LNCS).

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Algebraic Presentation of Semifree Monads

AU - Rosset, Aloïs

AU - Hansen, Helle Hvid

AU - Endrullis, Jörg

N1 - Funding Information: 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). Publisher Copyright: © 2022, IFIP International Federation for Information Processing.

PY - 2022

Y1 - 2022

N2 - 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 Ms 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.

AB - 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 Ms 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.

KW - algebraic presentation

KW - algebraic theory

KW - monad

KW - semifree

UR - http://www.scopus.com/inward/record.url?scp=85135018645&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85135018645&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-10736-8_6

DO - 10.1007/978-3-031-10736-8_6

M3 - Conference contribution

AN - SCOPUS:85135018645

SN - 9783031107351

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 110

EP - 132

BT - Coalgebraic Methods in Computer Science

A2 - Hansen, Helle Hvid

A2 - Zanasi, Fabio

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th IFIP WG 1.3 International Workshop on Coalgebraic Methods in Computer Science, CMCS 2022, colocated with European Joint Conference on Theory and Practice of Software, ETAPS 2022

Y2 - 2 April 2022 through 3 April 2022

ER -

Rosset A, Hansen HH, Endrullis J. Algebraic Presentation of Semifree Monads. In Hansen HH, Zanasi F, editors, Coalgebraic Methods in Computer Science: 16th IFIP WG 1.3 International Workshop, CMCS 2022, Colocated with ETAPS 2022, Munich, Germany, April 2-3, 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 110-132. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2022 Jul 23. doi: 10.1007/978-3-031-10736-8_6