2021/06/08 by Evan Patterson, Owen Lynch, James Fairbanks · 2 voices · 4 citations
Computer Science · #cs.DB #cs.LO #math.CT
paper · pdf · doi:10.32408/compositionality-4-5
Many mathematical objects can be represented as functors from finitely-presented categories C to Set. For instance, graphs are functors to Set from the category with two parallel arrows. Such functors are known informally as C-sets. In this paper, we describe and implement an extension of 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 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.