Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Interpreting slice categories in programming

Davi Sales Barreira (Dec 08 2023 at 15:02):

First let me give some context. I'm coding an application, and I'm trying to interpret within category theory. Thus, I've started by assuming that the programming code was in the category of sets, with types as sets, and programming functions as mathematical functions in set-theory.

From that, I've coded a free monad $D:\textbf{Set}\to \textbf{Set}$. Given a type $X$, an element of $DX$ is an expression tree where the leafs have values of type $X$.

In my code, I have an special type called $P$, which represents primitives. Given a type (set) $A$, I wanted to assign a function $\theta_A: A \to D P$, i.e. a function that receives a value of type $A$ and constructs an expression formed by primitives. After some discussion, some people pointed out that the whole thing could be seen as the slice category $\text{Kleisli}(D)/P$. Indeed, after inspection, they were right, and this interpretation fits nicely (I wanted the composition to work like it does in the Kleisli category).

Here is my new conundrum. I now want to use my monad $D$ to construct expression trees where the leafs have "type" $\text{Kleisli}(D)/P$, but $\text{Kleisli}(D)/P$ is a category not a set. Hence, I can't just interpret it as a type. I was wondering if there is a way to interpret this category in programming. My first idea was to somehow represent $\text{Kleisli}(D)/P$ as a set or perhaps as a subcategory within the category of sets. I thought of Yoneda lemma (which I am frankly still in the process of fully understanding).

David Egolf (Dec 08 2023 at 18:02):

I have a few thoughts/questions for you, as I'm trying to understand what you want to do:

1. $D: \mathsf{Set} \to \mathsf{Set}$ is a functor, right? I think you're saying it sends a set $X$ to the set $DX$ of all expression trees we can form (using some operators) where all the leaves are elements of $X$. If $f: X \to Y$ is a function, I'm wondering what $Df: DX \to DY$ is. Is this a function that takes in an expression tree, and then swaps out any occurrence of $x \in X$ with $f(x) \in Y$?
2. I think one idea you are describing is that a function $\theta_A: A \to DP$ tells us how to "build" any element $a \in A$ using a corresponding expression tree $\theta_A(a)$ which describes how to use "primitives" (elements of $P$) to make $a$. That seems really cool!

David Egolf (Dec 08 2023 at 18:04):

3. I'm trying to understand your last paragraph. If each function $\theta_A: A \to DP$ is like a collection of recipes for building elements of $a$ (and these functions are objects of $\mathrm{Kleisli}(D)/P$), then I guess that you are talking about sticking together different collections of recipes to make a fancier collection of recipes (with the "sticking together" process described by some new expression tree)?

David Egolf (Dec 08 2023 at 18:11):

This starts to remind me of composition in an operad, which looks like this:
composition in an operad

We could imagine the "wires" coming down the page as the different ingredients we need to build something, and each triangle as a process that uses a given recipe to build something new from these ingredients. (The image is from "Entropy and diversity" by Leinster).

I'm not sure how closely this relates to what you want to do.

Davi Sales Barreira (Dec 08 2023 at 19:01):

For 1., the answer is that $Df$ is the function that applies $f$ to each leaf of $DX$, turning it into a $DY$.

Davi Sales Barreira (Dec 08 2023 at 19:02):

About 3., yeah, it does sounds like operads. But I never quite understood operads and how to use them in programming.

Davi Sales Barreira (Dec 08 2023 at 19:03):

Thus I just went another route. I ended up with the idea of the free monad $D$.

David Egolf (Dec 08 2023 at 19:23):

Thanks for clarifying!

I still don't think I quite understand what you want to do. Is a tree where the leaves are objects from $\mathrm{Kleisli}(D)/P$ the sort of thing you are looking for?

Davi Sales Barreira (Dec 08 2023 at 19:27):

Yes. For example, in $DP$ I have $p1 + p2 + p3$. Which is an expression that says "draw $p1$ then $p2$ then $p3$". I want to have $(a \in A,\theta_A) + (b \in B,\theta_B) + (c \in C, \theta_C)$.

Davi Sales Barreira (Dec 08 2023 at 19:27):

Which is an expression constructed using $D$, but applying to the object in the slice category.

Davi Sales Barreira (Dec 08 2023 at 19:29):

Note that this expression can be translated into $DP$ by applying $\theta$, e.g. $\theta_A(a) + \theta_B(b) + \theta_C(c)$ gives me an expression of expressions i.e. $DDP$. Since $D$ is a monad, I can simply use $\mu$, thus, $\mu (\theta_A(a) + \theta_B(b) + \theta_C(c))$ returns a $DP$.

Davi Sales Barreira (Dec 08 2023 at 19:30):

This interests me because it means I can construct complex expressions in $DP$ using the "encapsulations".

Davi Sales Barreira (Dec 08 2023 at 19:30):

Makes sense?

Davi Sales Barreira (Dec 08 2023 at 19:31):

This has be clumsly coded, but it works... I'm now trying to find a categorical justification

Davi Sales Barreira (Dec 08 2023 at 19:33):

David Egolf said:

Thanks for clarifying!

I still don't think I quite understand what you want to do. Is a tree where the leaves are objects from $\mathrm{Kleisli}(D)/P$ the sort of thing you are looking for?

Perhaps my example clarified that the leafs have "types"that are objects in $\text{Kleisi(D)}/P$, they are not directly the objects.

Davi Sales Barreira (Dec 08 2023 at 19:35):

I guess the idea is similar to saying that I want to use $D \text{Monoid}$ which should mean that I want to construct a tree where each leave is a monoid, but each monoid can be distinct (e.g. one can be a list of strings, the other can be the integers using sum, and so on).

David Egolf (Dec 08 2023 at 19:49):

Davi Sales Barreira said:

Yes. For example, in $DP$ I have $p1 + p2 + p3$. Which is an expression that says "draw $p1$ then $p2$ then $p3$". I want to have $(a \in A,\theta_A) + (b \in B,\theta_B) + (c \in C, \theta_C)$.

I'm still working on reading the rest of what you said, but these tuples remind me a lot of the "category of elements" construction. If we have a "forgetful" functor $U: \mathrm{Kleisli}(D)/P \to \mathsf{Set}$ that sends $\theta_A: A \to DP$ to just $A$, then an object in the category of elements for $U$ is a tuple $(\theta_A, a)$, where $a \in U(\theta_A) = A$.

David Egolf (Dec 08 2023 at 19:50):

Here's the definition, for convenience (from "Category theory in context"):
category of elements

David Egolf (Dec 08 2023 at 19:55):

If I understand what you are saying, you want to construct trees where the leaves are tuples of this kind. (These trees encode expressions combining these tuples). If so, I think you are looking for trees having leaves that are objects in the category of elements of $U: \mathrm{Kleisli}(D)/P \to \mathsf{Set}$.

Davi Sales Barreira (Dec 08 2023 at 20:00):

Hmm, I'm not sure. I'll have to think about it.