List Objects with Algebraic Structure
View / Open Files
Editors
Dale Miller
Publication Date
2017-09Journal Title
LIPIcs : Leibniz International Proceedings in Informatics
Conference Name
2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017)
ISSN
1868-8969
Publisher
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Volume
84
Number
16
Type
Conference Object
This Version
VoR
Metadata
Show full item recordCitation
Fiore, M., & Saville, P. (2017). List Objects with Algebraic Structure. LIPIcs : Leibniz International Proceedings in Informatics, 84 (16)https://doi.org/10.4230/LIPIcs.FSCD.2017.16
Abstract
We introduce and study the notion of list object with algebraic structure. The first key aspect of our development is that the notion of list object is
considered in the context of monoidal structure; the second key aspect is that we further equip list objects with algebraic structure in this setting. Within our framework, we observe that list objects give rise to free monoids and moreover show that this remains so in the presence of algebraic structure. Furthermore, we provide a basic theory explicitly describing as an inductively defined object such free monoids with suitably compatible algebraic structure in common practical situations. This theory is accompanied with the study of two technical themes that,
besides being of interest in their own right, are important for establishing
applications. These themes are: parametrised initiality, central to the universal property defining list objects; and approaches to algebraic structure, in particular in the context of monoidal theories. The latter leads naturally to a notion of nsr (or near semiring)
category of independent interest. With the theoretical development in place, we touch upon a variety of applications, considering Natural Numbers Objects in domain theory, giving a universal property for the monadic list transformer, providing free instances of algebraic extensions of the Haskell Monad type class, elucidating the algebraic character of the construction of opetopes in higher-dimensional algebra, and considering free models of second-order algebraic theories.
Keywords
list object, free monoid, strong monad, (cartesian,linear, and second-order) algebraic theory, near semiring, Haskell Monad type class, opetope
Sponsorship
EPSRC (1649725)
Identifiers
External DOI: https://doi.org/10.4230/LIPIcs.FSCD.2017.16
This record's URL: https://www.repository.cam.ac.uk/handle/1810/267327
Rights
Attribution 4.0 International, Attribution 4.0 International, Attribution 4.0 International
Recommended or similar items
The following licence files are associated with this item: