Dioids for computational effects

Abstract

There are different algebraic structures that one can use to model notions of computation. The most well-known are monads, but lately, applicative functors have been gaining popularity. These two structures can be understood as instances of the unifying notion of monoid in a monoidal category. When dealing with non-determinism, it is usual to extend monads and applicative functors with additional structure. However, depending on the desired non-determinism, there are different options of interaction between the existing and the additional structure. This article studies one of those options, which is captured algebraically by dioids. We generalise dioids to dioid categories and show how dioids in such a category model nondeterminism in monads and applicative functors. Moreover, we study the construction of free dioids in a programming context.