Is there a concept formalizing variables in expression trees under Category Theory?

53 Views Asked by At

Consider a free algebra over operations $\times$ and $+$ under a set $A$. If I understand correctly, one can think of this using a free monad $Free D$ such that $Free D (A)$ is the set of all finite expressions generated from theses operations over $A$, e.g. $a +a$, $a+(a*(a+a)))$, and so on.

Consider now these expression trees with variables, e.g: $$ f(x,y): = (x + a)*(a + y) + x*y $$ The idea is that we can plug values $x, y \in Free D$ such that we get a "valid tree". For example, for $x = (a + b)$ and $y = c$ where $a,b,c \in A$, we have: $$ f(x,y) = ((a+b) + a)*(a + (c)) + (a+b)*(c) $$

What is the Category Theoretical understanding of these types of functions? Is there any field/name/concept dealing with them? Or is this just too generic to have a "name"?

1

There are 1 best solutions below

2
On BEST ANSWER

$Free D(A)$ is already the set of expression trees whose variables belong to the set $A$. E.g. $f(x,y):=(x+a)*(a+y)+x*y$ is an element of $Free D(\{x,y,a\})$, taking $x=a+b$ and $y=c$ corresponds to a function $\{x,y\}\to Free D(\{a,b,c\})$. The latter factors through a function $\{x,y,a\}\to FreeD(\{a,b,c\})$. The fact that $FreeD(\{x,y,a\})$ is the free algebra requires that the function $\{x,y,a\}\to FreeD(\{a,b,c\})$ factors as $\{x,y,a\}\to Free D(\{x,y,a\}\to FreeD(\{a,b,c\})$ for a unique homomorphism $Free D(\{x,y,a\}\to FreeD(\{a,b,c\})$. That homomorphism in particular sends $f(x,y)=(x+a)*(a+y)+x*y$ to $f(a+b,c)=((a+b)+a)*(a+(c))+(a+b)*(c)$.