1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ In order to rule out trivial edge cases, could you sketch what categories you have in mind for domain and codomain for those functors? $\endgroup$ Jun 10, 2023 at 14:21

1 Answer 1

4
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Cow is otherwise known as subset, or characteristic function. Are those not mathematically sensible data structures? $\endgroup$ Jun 12, 2023 at 14:14
  • $\begingroup$ 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. $\endgroup$
    – Dan Doel
    Jun 12, 2023 at 14:55
  • $\begingroup$ @DanDoel Cow can be seen as a key-value store with $\mathbb{B}$ being the value set. $\endgroup$ Jun 12, 2023 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.