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.
Mike Stay (Apr 20 2021 at 18:48):There's a good notion of the derivative of a data type or a species. @Marcelo Fiore and @Tom Leinster's paper Objects of categories as complex numbers uses ring theory to say when we can think of a data type as having a complex cardinality.
"Setting the derivative to zero" lets us pick out critical points of functions—maxima, minima, and inflection points—but does it have any combinatorial meaning other than finding a critical point of the cardinality of the data type? Flajolet and Sedgewick's Analytic Combinatorics spends all of section VIII on saddle points, which in many circumstances can be used to put upper bounds on the growth of the sequence, but I feel like there's got to be something more going on here.
One idea I had was to use the fact that the cardinality is related to Euler characteristic; for instance, binary strings have cardinality -1 and can be thought of as a "poor man's interval". Adding one point to compactify it, we get something with cardinality 0. How is a circle related to the critical points of a data type? Does it have something to do with loop space?
Jacques Carette (Apr 20 2021 at 20:11):I would look deep in Algorithms for Combinatorial Systems: Well-Founded Systems and Newton Iterations for hints to that. Bruno Salvy was a PhD student of Flajolet's, and uses Species throughout this particular paper.
Note that the derivative a data type should really be understood as a tangent space, not a "derivative" in the usual functional sense. It's misleading that it can be computed via the derivative of a Functor using the usual rules of differentiation. [It is not wrong that it is computed that way, merely that it tends to prime the wrong neurons when looking at it too quickly.]
Mike Stay (Apr 20 2021 at 21:06):Thanks, I'll have a look.
tangent space
That's encouraging, since my end goal is to understand the combinatorial content of Lagrangian mechanics.
John Baez (Apr 20 2021 at 22:51):That sounds like a great goal, Mike. Hard, but potentially great.
fosco (Apr 21 2021 at 05:29):Jacques Carette said:
I would look deep in Algorithms for Combinatorial Systems: Well-Founded Systems and Newton Iterations for hints to that. Bruno Salvy was a PhD student of Flajolet's, and uses Species throughout this particular paper.
Note that the derivative a data type should really be understood as a tangent space, not a "derivative" in the usual functional sense. It's misleading that it can be computed via the derivative of a Functor using the usual rules of differentiation. [It is not wrong that it is computed that way, merely that it tends to prime the wrong neurons when looking at it too quickly.]
I don't think this is misleading, but tell me more! I might be interested in drawing a (dis)connection between the two meanings of "derivative"
Jacques Carette (Apr 21 2021 at 17:48):I'm going to stick to the intuitive level in my answer. Think of derivative from the differential geometry point of view: to a map f from a manifold M to a manifold N, it associates to each 'point' m of M a linear map from the tangent space to .
I think of a data-structure as a space - a highly structured space (rather like a manifold). But the addresses of a manifold are different, in that functions on a manifold are defined directly on them. I'm using address in the same sense that gets given 'addresses' when choosing a cartesian coordinate system. From the functional point of view, one view of data structures also associates addresses to each location - this is the 'containers' view. What's different is that data-structures contain data at those addresses. One could just say that this is a function from addresses to some value space - and this is indeed a valid way to look at it. But it's a bit odd, since usually this function is "maximally wild": it is essentially a random function. You really do want fully arbitrary data in your lists, arrays, even trees (though sometimes you do want balanced binary trees of ordered data - but still, within that constraint, the data is still wild). This is rarely so for a function on a manifold, which tends to be specified via a rather small amount of data. Asking that such functions be smooth is quite a restriction.
So the analog of computing a derivative of a data-structure is the analog of mapping from to . There is also an associated analog of derivatives on functions, which is where all the fuss around AD comes from. What's easy to forget in traditional AD is that the tangent space to can be naturally identified with . To me, that's an annoying coincidence. [The work on tangent categories and differential categories does treat that correctly]
Some of this is present in @Conal Elliott 's work - but I remember discussions of this on Google Buzz circa 2011. I think it was @Paolo G. Giarrusso who might have pointed me to it.
I am currently actively working on ideas in these circle of ideas with a PhD student. I don't want to give too much away quite yet, but we're hoping to release a preprint soon.