Skip to main content

Complexity bounds for container functors and comonads

Orchard, Dominic A. (2018) Complexity bounds for container functors and comonads. Information and Computation, . ISSN 0890-5401. (doi:10.1016/j.ic.2018.05.008)

PDF - Publisher pdf

Creative Commons Licence
This work is licensed under a Creative Commons Attribution 4.0 International License.
Download (854kB) Preview
[img]
Preview
PDF - Author's Accepted Manuscript

Creative Commons Licence
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Download (328kB) Preview
[img]
Preview
Official URL
https://doi.org/10.1016/j.ic.2018.05.008

Abstract

The notion of containers, due to Abbott et al., characterises a subset of parametric data types which can be described by a set of shapes and a set of positions for each shape. This includes common data types such as tuples, lists, trees, arrays, and graphs. Various useful categorical structures can be derived for containers that have some additional structure on their shapes and positions. For example, the notion of a directed container (due to Ahman et al.) gives rise to container comonads. Containers, and refinements such as directed containers, provide a useful reasoning tool for data types and an abstraction mechanism for programming, e.g., building libraries parameterised over containers. This paper studies the performance characteristics of traversal schemes over containers modelled by additional functor and comonad structure. A cost model for container transformations is defined from which complexity bounds for the operations of container functors and comonads are derived. This provides a reasoning principle for the performance of programs structured using these idioms, suggesting optimisations which follow from the underling mathematical structure. Due to the abstract interface provided by the syntax of containers and category theory, the complexity bounds and subsequent optimisations they imply are implementation agnostic (machine free). As far as we are aware, this is the first such study of the performance characteristics of containers.

Item Type: Article
DOI/Identification number: 10.1016/j.ic.2018.05.008
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Faculties > Sciences > School of Computing
Depositing User: Dominic Orchard
Date Deposited: 05 Apr 2018 15:37 UTC
Last Modified: 29 May 2019 20:26 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/66631 (The current URI for this page, for reference purposes)
Orchard, Dominic A.: https://orcid.org/0000-0002-7058-7842
  • Depositors only (login required):

Downloads

Downloads per month over past year