Categorical Data Structures for Technical Computing

Many mathematical objects can be represented as functors from finitely-presented categories \(\mathsf{C}\) to \(\mathsf{Set}\). For instance, graphs are functors to \(\mathsf{Set}\) from the category with two parallel arrows. Such functors are known informally as \(\mathsf{C}\)-sets. In this paper,...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-07
Main Authors: Patterson, Evan, Lynch, Owen, Fairbanks, James
Format: Article
Language:English
Subjects:
Apexes
Data structures
Graph theory
Graphs
Mathematical analysis
Petri nets
Programming languages
Rate constants
Wiring
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Many mathematical objects can be represented as functors from finitely-presented categories \(\mathsf{C}\) to \(\mathsf{Set}\). For instance, graphs are functors to \(\mathsf{Set}\) from the category with two parallel arrows. Such functors are known informally as \(\mathsf{C}\)-sets. In this paper, we describe and implement an extension of \(\mathsf{C}\)-sets having data attributes with fixed types, such as graphs with labeled vertices or real-valued edge weights. We call such structures "acsets," short for "attributed \(\mathsf{C}\)-sets." Derived from previous work on algebraic databases, acsets are a joint generalization of graphs and data frames. They also encompass more elaborate graph-like objects such as wiring diagrams and Petri nets with rate constants. We develop the mathematical theory of acsets and then describe a generic implementation in the Julia programming language, which uses advanced language features to achieve performance comparable with specialized data structures.
ISSN:2331-8422
DOI:10.48550/arxiv.2106.04703