# The category of sets and “stateful” functions

In some programming languages, there's functions whose output can change on the basis of changing internal state; for example, the second time you compute $f(5)$ you might get a different answer. This doesn't really happen in mathematics. Nonetheless, I'd like to better understand the extent to which mathematics relies on the "statelessness" of mathematical functions.

To this end, define:

Definition 0. Given a set $X$, view the Kleene closure $X^*$ as an $(\mathbb{N},\leq)$ presheaf as follows:

• $X^*(n) = \{x \in X^* \mid \mathrm{length}(x) = n\} \cong X^n$
• If $\varphi:a \leq b$, then $X^*(\varphi) : X^*(b) \rightarrow X^*(a)$ is the restriction map that takes the first $a$-many letters of the word and deletes the rest.

Definition 1. Given sets $X$ and $Y$, a stateful function $X \rightarrow Y$ is a natural transform $X^* \rightarrow Y^*$, where $X^*$ is the set of all words in $X$. Write $\mathbf{Set}^*$ for the category whose objects are sets and whose morphisms are stateful functions.

My questions are whether or not this has been studied, and in particular, whether or not there is a sensible answer to the admittedly rather vague question: "What is the internal logic of $\mathbf{Set}^*$?"

• As you admit yourself, the question is rather vague, so I don't know how to answer. Still, in case it helps to clarify something - your $\mathbf{Set}^*$ seems to be isomorphic to the coKleisli category of the comonad structure on $\_^*$, with $\varepsilon(x_1,...,x_n)=x_n$ and $\delta(x_1,...,x_n)=((x_1),...,(x_1,...,x_n))$. – მამუკა ჯიბლაძე Aug 20 '16 at 7:53
• This seems to be essentially the theory of polymorphic list operations ---as in functional programming--- and there's a host of categorical results there. As for the internal logic, in computer science, lists are used as naive representations for relations and so looking in that direction may be fruitful. – Musa Al-hassy Aug 20 '16 at 18:51
• It is unclear what you mean by "natural transform $X*\to Y^*$". Do you mean "natural transformations between the functors from the functor $X\mapsto X^*$ to $Y\mapsto Y^*$? If yes, note that all pairs of sets $(X,Y)$ have the same hom-set. If no, what's a natural transform? – Thorsten Aug 7 '17 at 13:25
• And in programming, stateful functions are modelled using the Kleisli-Category of the state monad. – Thorsten Aug 7 '17 at 13:27
• $\DeclareMathOperator\Hom{Hom}$@Thorsten, I think I must misunderstand your [comment](mathoverflow.net/questions/247891/…). What does "all pairs of sets $(X, Y)$ have the same hom-set" mean? Surely $\Hom_{\mathbf{Set}}(\emptyset, {*}) \ne \Hom_{\mathbf{Set}}({*}, \emptyset)$? – LSpice Mar 25 at 21:16