Categories for Collection Monads

In 1998 Manes introduced the notion of collection monad on the category of sets as a suitable semantics for collection types. The canonical example of collection monad is the finite powerset monad.

In order to account for the algorithmic aspects the category of sets should be replaced with other categories, whose arrows are maps computable by “low complexity” algorithms.

We give a systematic way to construct such models, inspired by realizability, which include categories whose arrows are “low complexity” functions between countable sets.