<p>To give a context to your question, let us formulate it mathematically. For simplicity I shall work with the category of sets <span class="math-container">$\mathsf{Set}$</span>, but it ought to be clear that one can replace it with many other categories.</p>
<p>We need a reasonable notion of “data structure“. Given the question, it is safe to assume that you have in mind what is usually called a <em>type constructor</em>, i.e., a map <span class="math-container">$F : \mathsf{Set} \to \mathsf{Set}$</span> which takes a type <span class="math-container">$X$</span> (or a set) and returns a type <span class="math-container">$F(X)$</span> (or a set). Some examples:</p>
<ul>
<li><span class="math-container">$\mathsf{List}(X)$</span>, the set of all finite lists of elements of <span class="math-container">$X$</span>,</li>
<li><span class="math-container">$\mathsf{Tree}(X)$</span>, the set of finite binary trees with nodes labeled by elements of <span class="math-container">$X$</span>,</li>
<li><span class="math-container">$X \mapsto X \times X$</span></li>
<li><span class="math-container">$X \mapsto \mathsf{Nat} + X$</span></li>
<li>etc.</li>
</ul>
<p>Can these always be extended to functors?</p>
<p>Here is an example that cannot be extended to a functor:
<span class="math-container">$$
F(X) =
\begin{cases}
X &amp; \text{if $X$ has at most one element}, \\
\emptyset &amp; \text{if $X$ has more than one element}
\end{cases}
$$</span>
Indeed, consider <span class="math-container">$f : \{0\} \to \{0,1\}$</span>, <span class="math-container">$f(0) = 0$</span>. It would have to be mapped by <span class="math-container">$F$</span> to some function <span class="math-container">$F(f) : F(\{0\}) \to F(\{0,1\})$</span>, but this is impossible because <span class="math-container">$F(\{0\}) = \{0\}$</span> and <span class="math-container">$F(\{0,1\}) = \emptyset$</span>.
However, nobody would call such an <span class="math-container">$F$</span> a &quot;data structure&quot;.</p>
<p>So long as data structures are built from basic operations that <em>are</em> functorial, they will be functors. The following are all functorial:</p>
<ul>
<li>cartesian products <span class="math-container">$\times$</span> and sums <span class="math-container">$+$</span></li>
<li>constant types</li>
<li>formation of an inductive type</li>
<li>formation of a co-inductive type</li>
</ul>
<p>This covers a lot of ground (tuples, lists, trees, streams, etc.), but not everything, for instance <em>function spaces</em> and general <em>recursive types</em>. We can still save the day by observing that function space <span class="math-container">$F(X, Y) = (X \to Y)$</span> is <em>contravariant</em> in <span class="math-container">$X$</span> and <em>covariant</em> in <span class="math-container">$Y$</span>, so we do get a functor
<span class="math-container">$$F : \mathsf{Set}^\mathrm{op} \times \mathsf{Set} \to \mathsf{Set}.$$</span>
(Recursive types can be treated similarly.)</p>
<p>A concrete example of a reasonable datastructure that is not functorial is one that combines covariance and contravariance, e.g., a datum paired with a predicate:</p>
<pre><code>data Cow a = Moo { horn :: a, tail :: a -&gt; Bool }
</code></pre>
<p>The <code>horn</code> field is covariant, the <code>tail</code> is contravariant, so we do not have a functor anymore.</p>
<p>One possible answer to your question is: if it isn't functorial, then it isn't mathematically sensible, so why are you calling it a data structure?</p>

CC BY-SA 4.0
2023-06-12T14:14:36.123Z
*Cow* is otherwise known as *subset*, or *characteristic function*. Are those not mathematically sensible data structures?
Martin Berger
CC BY-SA 4.0
2023-06-12T14:55:02.580Z
I don't know if I'd call `Cow` a data structure. But there are plenty of genuine data structures that are not functors so easily. For instance, binary search trees and heaps are not functorial (in the keys) unless you adjust the categories somehow (so that all objects are equipped with decidable orders, or all maps are monotone, etc.). Those will actually be encountered in introductory data structures courses, so it seems like a mathematical theory of data structures had better handle them.
Dan Doel
CC BY-SA 4.0
2023-06-12T15:01:53.347Z
@DanDoel `Cow` can be seen as a key-value store with $\mathbb{B}$ being the value set.
Martin Berger
CC BY-SA 4.0
2023-06-10T20:13:15.480Z
2023-06-10T22:24:32.750Z
2023-06-10T22:24:32.750Z
Andrej Bauer
<p>The justification of my conjecture is that (seemly) any data structure can have a mapper that applies a given function <span class="math-container">$f$</span> to each element of the structure. A data structure in the end is a container of data (is this true?) and we can modify the data point-wisely, so a functor mapping. The identity and associative properties are also satisfied obviously. So, can I say any data structure is a functor?</p>
<p>I fail to think up a counter-example, nor, find support from literatures.</p>

CC BY-SA 4.0
2023-06-10T14:21:01.217Z
In order to rule out trivial edge cases, could you sketch what categories you have in mind for domain and codomain for those functors?
Martin Berger
<pl.programming-languages><ds.data-structures>
Is data structure necessarily a functor?
XQY
# Is data structure necessarily a functor?

(Asked by: username_0 on 2023-06-10)

The justification of my conjecture is that (seemly) any data structure can have a mapper that applies a given function $f$ to each element of the structure. A data structure in the end is a container of data (is this true?) and we can modify the data point-wisely, so a functor mapping. The identity and associative properties are also satisfied obviously. So, can I say any data structure is a functor?

I fail to think up a counter-example, nor, find support from literatures.

**Tags:** pl.programming-languages, ds.data-structures

> **Comments:**
> **username_1**: In order to rule out trivial edge cases, could you sketch what categories you have in mind for domain and codomain for those functors?  

---

## 1 answers

### Answer by username_2 on 2023-06-10. Score: 4

To give a context to your question, let us formulate it mathematically. For simplicity I shall work with the category of sets $\mathsf{Set}$, but it ought to be clear that one can replace it with many other categories.
We need a reasonable notion of “data structure“. Given the question, it is safe to assume that you have in mind what is usually called a type constructor, i.e., a map $F : \mathsf{Set} \to \mathsf{Set}$ which takes a type $X$ (or a set) and returns a type $F(X)$ (or a set). Some examples:

$\mathsf{List}(X)$, the set of all finite lists of elements of $X$,
$\mathsf{Tree}(X)$, the set of finite binary trees with nodes labeled by elements of $X$,
$X \mapsto X \times X$
$X \mapsto \mathsf{Nat} + X$
etc.

Can these always be extended to functors?
Here is an example that cannot be extended to a functor:
$$
F(X) =
\begin{cases}
X & \text{if $X$ has at most one element}, \\
\emptyset & \text{if $X$ has more than one element}
\end{cases}
$$
Indeed, consider $f : \{0\} \to \{0,1\}$, $f(0) = 0$. It would have to be mapped by $F$ to some function $F(f) : F(\{0\}) \to F(\{0,1\})$, but this is impossible because $F(\{0\}) = \{0\}$ and $F(\{0,1\}) = \emptyset$.
However, nobody would call such an $F$ a "data structure".
So long as data structures are built from basic operations that are functorial, they will be functors. The following are all functorial:

cartesian products $\times$ and sums $+$
constant types
formation of an inductive type
formation of a co-inductive type

This covers a lot of ground (tuples, lists, trees, streams, etc.), but not everything, for instance function spaces and general recursive types. We can still save the day by observing that function space $F(X, Y) = (X \to Y)$ is contravariant in $X$ and covariant in $Y$, so we do get a functor
$$F : \mathsf{Set}^\mathrm{op} \times \mathsf{Set} \to \mathsf{Set}.$$
(Recursive types can be treated similarly.)
A concrete example of a reasonable datastructure that is not functorial is one that combines covariance and contravariance, e.g., a datum paired with a predicate:
data Cow a = Moo { horn :: a, tail :: a -> Bool }

The horn field is covariant, the tail is contravariant, so we do not have a functor anymore.
One possible answer to your question is: if it isn't functorial, then it isn't mathematically sensible, so why are you calling it a data structure?

> **Comments:**
> **username_1**: *Cow* is otherwise known as *subset*, or *characteristic function*. Are those not mathematically sensible data structures?  
> **username_3**: I don't know if I'd call `Cow` a data structure. But there are plenty of genuine data structures that are not functors so easily. For instance, binary search trees and heaps are not functorial (in the keys) unless you adjust the categories somehow (so that all objects are equipped with decidable orders, or all maps are monotone, etc.). Those will actually be encountered in introductory data structures courses, so it seems like a mathematical theory of data structures had better handle them.  
> **username_1**: @DanDoel `Cow` can be seen as a key-value store with $\mathbb{B}$ being the value set.  

---

