2023/01/25 by Kozen, Dexter, Silva, Alexandra
#D.3.1 #F.3.2 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Programming Languages (cs.PL)
paper · doi:10.48550/arxiv.2301.10812
We give a lightweight alternative construction of Jacobs's distributive law for multisets and distributions that does not involve any combinatorics. We first give a distributive law for lists and distributions, then apply a general theorem on 2-categories that allows properties of lists to be transferred automatically to multisets. The theorem states that equations between 2-cells are preserved by epic 2-natural transformations. In our application, the appropriate epic 2-natural transformation is defined in terms of the Parikh map, familiar from formal language theory, that takes a list to its multiset of elements.