20
$\begingroup$

Disclaimer: I am not a CS theorist.

Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data structures. I first thought that straight up set theoretical bijective morphisms would suffice, but I ran into a wall quite rapidly - those are just encodings and do not capture the computational essence of the data structure.

Is there a more restrictive (but more useful) definition? (Or if not, why?) Is there a canonical definition of category of "constructed data structures"?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
16
$\begingroup$

There is not a canonical such category, for the same reason there is no canonical category of computations. However, there are large and useful algebraic structures on data structures.

One of the more general such structures, which is still nevertheless useful, is the theory of combinatorial species. A species is a functor $F : B \to B$, where $B$ is the category of finite sets and bijections between them. You can think of species as being families of structures indexed by abstract sets of locations. This explains the functoriality over $B$ -- such families have to be invariant with respect to renaming the abstract labels. Then, the calculus of species basically replays generating function methods at the functorial level, to generate sets of data structures instead of counts.

To see this theory implemented in a programming language, you can read Brent Yorgey's Haskell Symposium paper, Species and functors and types, oh my!. I think Sage also has a species package, though of course it's oriented towards computer algebra rather than programming.

Improve this answer
$\endgroup$
15
$\begingroup$

Indeed, there is a different notion than isomorphism which is more useful in programming. It is called "behavioural equivalence" (sometimes called "observational equivalence") and it is established by giving a "simulation relation" between data structures rather than bijections. Algebraists came in and established an area called "algebraic data types" in Computer Science, where they pushed isomorphisms and initial algebras for a while. Eventually, Computer Scientists realized that they were being misled. A good paper that talks about these issues is "On observational equivalence and algebraic specification" by Sannella and Tarlecki.

I wrote an answer to another question in cstheory on logical relations and simulations which talks about the more general history of simulation relations in Computer science. You are welcome to read that and follow up on the references given there. The Chapter 5 of Reynolds's "Craft of Programming" is particularly enlightening.

A text book on Algebraic Automata Theory by Holcombe has the following interesting quote (p. 42):

There are many other results concerned with homomorphisms and quotients... While they are of independent algebraic interest they have not yet proved particularly useful in the study of automata and related areas. In fact, the algebraic theory of machines diverges from the direction taken in other algebraic theories in one important respect... The emphasis in automata theory is, however, not [on] what machines "look like" but what "they can do". We will regard two machines as being very closely related if they can both "do the same thing", they may however not be algebraically isomorphic!

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Pondering the Holcombe quote some more, I notice that he is basically saying that traditional algebra deals with what things "look like", i.e., their structure, but they have no handle on what "they can do", i.e., their behaviour. This seems to point to a fundamental limitation of traditional algebra with respect to Computer Science. Sadly, I think Category Theory also belongs in the same camp. But Category Theory has a "holy cow" status and talking about its limitations is considered uncool. Hopefully, Computer Scientists will gather enough courage to say it more loudly. $\endgroup$
    – Uday Reddy
    Commented Mar 10, 2012 at 9:19
  • $\begingroup$ Uday, could you elaborate some more on how (the assymetry?) of the category theory seems not a good fit? $\endgroup$
    – Łukasz Lew
    Commented Apr 29, 2018 at 5:55
  • $\begingroup$ @ŁukaszLew, If category theory were a good fit, you would be able to say that all typed lambda calculus type expressions with a type variable X are functors. But they are not, e.g., F(X) = (X -> X) is not a functor. $\endgroup$
    – Uday Reddy
    Commented Jun 6, 2018 at 14:59
  • $\begingroup$ Typed lambda calculus is effectively the internal language of cartesian closed categories C. Function types likes (X->A) are the "exponential objects" or "internal homs" in such categories. Their construction is a functor (X,A) |-> (X->A) : C^op x C --> C just as it should be. The diagonal X |-> (X ->X) is still a functor on the groupoid core of C. Just as it should be. There is little room for category theory not to be a "good fit" for programming theory. $\endgroup$
    – Urs Schreiber
    Commented Jan 26, 2023 at 16:27
7
$\begingroup$

Rather than ask how we can strengthen/weaken the notion of isomorphism, another possibility is to ask: What is the right notion of equivalence between computational structures, and what is the mathematical structure underlying this notion.

One large family of structures is coalgebras. Structures such as lists, trees, automata, both of the finite and infinite variety can be described as coalgebras. We can then study homomorphism or isomorphism between coalgebras.

However, even homomorphisms between coalgebras don't tell the whole story. You may find it helpful to look up simulations, bisimulations and other logical relations. If you strictly prefer an algebraic approach (as opposed to a relational one) Galois connections are one option. Here are some starting points.

Improve this answer
$\endgroup$
2
$\begingroup$

Disclaimer: I'm not sure I understood your question. Do you want to talk about isomorphism between two data structures, or between two "data structure specifications"? (These are sometimes called Abstract Data Types.)

If you consider the cell probe model, then I think a concept of isomorphism easily arises. That is because the cell probe model models computation by a decision tree, so isomorphism is easy to define. The cell probe model would help, I think, both if you consider isomorphism between data structure implementations, and if you consider data structure specifications.

For information on the cell probe model, see e.g. the survey of Miltersen. (Cell Probe Complexity: A Survey)

If you say more about why you need to define isomorphism between data structures, it might be possible to provide more help. Feel free to message me.

Improve this answer
$\endgroup$

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.