Monad composition · theory: category theory

I was a member of The Perimeter Institute in 2003. My advisor was Lucien Hardy. I was a student of and research assistant to Prakash Panangaden in 2009.

I am working on a derivation of a new form of quantum theory that is relevant to quantum gravity. It requires a monad composition. These are very tricky and we have seen Zwart et al. warn against going head on without real care. I have shown my general framework to a major titan in category theory for probability and he says it is time for me to proceed with applying it to new physics, which is what this post is about. I would like to invite the community to message me and help me with the monad composition.

Ralph Sarkis (Feb 04 2023 at 19:06):

Maaike Zwart's thesis has quite a lot of information on how to compose monads from the algebraic perspective, and the references should have just as much on the categorical perspective.

Another possible place to look is chapter 2 of Alexandre Goy's thesis and his paper just in case the monads you are studying do not compose "perfectly".

Ben Sprott (Feb 04 2023 at 19:45):

Hey, I just want to keep it a bit secret for now. I mean, I already have a math overflow about the composition and no one will answer it. Now, I just want someone to take a personal interest in it and contact me.

Ben Sprott (Feb 04 2023 at 19:46):

David Michael Roberts (Feb 05 2023 at 01:49):

Hi Ben. I was trying to unpack your question on MO, and find out what your actual definitions were, but it never got resolved in the end. It's not so much that no one will answer it, but it's not clear how to answer it, without either divining your 'secret' definition that accords with your physics intuition, or doing the hard work of trying to invent something that will work, but not being what you were thinking of. Or else perhaps it just doesn't work! Who knows, at this point, without extra detail. I do wish you success, but it will probably require some much more probing discussion to see what your intuition is telling you.

Ben Sprott (Feb 05 2023 at 18:51):

Hi David, I don't think there are any secret definitions. At least I didn't think there were, not for the monad composition. The multiset monad is well defined and I am borrowing the cyclic list right out of the paper by Kock. IIIRC there is some question about the cyclic list monad and its product natural transformation? This is because Kock's paper is just about the functor, and not the monad. It turns out that I asked Pieter Hofstra about this at his office in Ottawa, where I live. What a gentle genius he was. It was sad to hear of his passing. He helped a bit by suggesting the following:

That should take cyclic lists of cyclic lists to a set of cyclic lists in a natural way.

I guess this leaves the unit. My first guess for that is just like list, set elements go to singleton lists, a cyclic list with just one entry that points to itself.

Ralph Sarkis (Feb 05 2023 at 19:28):

I am having troubles convincing myself the multiplication is associative. Do you have a simple formal representation of cyclic lists? For example, a (non-cyclic) list can be seen as a number

n

and function

\{1,\dots,n\} \to X

, that is how we see the list functor as a polynomial

X \mapsto \sum X^n

. I guess you can take a quotient to see a cyclic list as an equivalence class of lists, but it would be easier if we had a simpler representation. I am unable to parse Kock's paper to understand what the polynomial is.

Ben Sprott (Feb 05 2023 at 20:46):

Hi Ralph, Thanks for the question. This goes back to what David was saying. Unfortunately, I have never seen anything like what you are asking for. We will have to define something. I am not too keen on working with polynomials since that complicates the matter. Multiset is not polynomial on Set, which is where I am working.

Ben Sprott (Feb 05 2023 at 20:50):

By tonight, I am going to release a rough paper that outlines everything I am doing and everything this calculation will really need. This is going to cover a huge, difficult scope in the category of monads on Set. The paper is intended to just give away the big idea at this point so that maybe people will be motivated to work on it.

Ben Sprott (Feb 05 2023 at 21:35):

David Michael Roberts (Feb 05 2023 at 22:09):

Can you give the complete definition of the underlying endofunctor

L_C\colon Set \to Set

, including what is does to functions between sets? And prove it's a functor? Kock writes down a different endofunctor, on

Gpd

, IIRC.

Before you talk about the multiplication of a putative monad, you need to know all about this endofunctor on

Set

David Michael Roberts (Feb 05 2023 at 23:57):

That is, if I give you a set

X

, what is the set

L_C(X)

? Is it the set of cyclic lists of elements of

X

? I cannot imagine it can be anything else, but you haven't specified and it might be something else, determined by the mental picture you have.

And then, given a function

f\colon X\to Y

between finite sets, what is the function

L_C(f)\colon L_C(X)\to L_C(X)

? Does it send a cyclic list

(x_1,\ldots,x_n) \in L_C(X)

(where I'm arbitrarily cutting the list, but you should think of this as only being defined up to a cyclic permutation) to the cyclic list

(f(x_1),\ldots,f(x_n))\in L_C(Y)

? Again, this has to match your mental picture, but you never wrote this down, so I can only make a guess.

You should prove to yourself that what I wrote down does indeed unambiguously describe a functor, even if it's not the one you mean, because that is either good practice or a warm-up to the functor that's in your head.

When writing this material up, it's crucial to write down these basic definitions because someone familiar with category theory might be able to start making guesses, which might be incorrect, but someone who is not familiar would have no way of even making a guess as to what you are talking about.

David Michael Roberts (Feb 06 2023 at 00:02):

At this point, one might try to write down what

L_C(L_C(X))

looks like, for a given set

X

, and then what an arbitrary component

L_C(L_C(X)) \to L_C(X)

of a natural transformation

L_C\circ L_C \Rightarrow L_C

looks like. Similarly with the unit natural transformation. Then one needs to check these do in fact form a monad on

Set

Ralph Sarkis (Feb 06 2023 at 08:26):

Here is an (sketch of an) attempt at defining

L_C

. My representation is based on graphs, but there are probably other ones. It seems to me it will be damned difficult to avoid using quotients, but I might be mistaken.

When I say graphs, I mean what graph theorists would call directed multigraphs with loops, and what category theorists would call presheaves on the category with two parallel morphisms $$V \rightrightarrow E$$. A moprhism

G \to H

is a pair of functions that send vertices to vertices and edges to edges such that the source (resp. target) of the image edge is the image of the source (resp. target) of the original edge (basically it is a functor when you forget about composition and identities).

Now, we can describe a cycle of size

n

in a graph

G

as a morphism

C_n \to G

, where

C_n

is the cycle on

n

vertices. With the same trick as for lists, we define the polynomial functor of cycles

L_C: \mathbf{Gph} \to \mathbf{Set} = G \mapsto \sum \mathrm{Hom}_{\mathbf{Gph}}(C_n,G)

A cyclic list over

X

induces a cycle in the complete graph

K_X

(it has

X

as its set of vertices and edges between all vertices). You can show

X \mapsto K_X

is a functor

K: \mathbf{Set} \rightarrow \mathbf{Gph}

. Unfortunately, this is not a perfect correspondence because a cycle in

K_X

has a start and end that coincide but mark a point which should not be marked for cyclic lists (as I understand it). Thus, we need to quotient

\mathrm{Hom}_{\mathbf{Gph}}(C_n,K_X)

with the relation

f \sim g \Leftrightarrow f = g \circ \sigma

where

\sigma: C_n \to C_n

is an isomorphism (you should check that these are exactly the rotations of the cycle).

After verifying that this quotient behaves well with respect to post-composition (the action of

\mathrm{Hom}_{\mathbf{Gph}}(C_n,-)

on morphisms), you can compose it with the functor

K

to get a functor

L_C : \mathbf{Set} \to \mathbf{Set} = X \mapsto \sum \mathrm{Hom}_{\mathbf{Gph}}(C_n, K_X)/{\sim}

Ralph Sarkis (Feb 06 2023 at 08:28):

After thinking about this a bit more, I don't think your description of the multiplication is natural. It seems like you are making a choice of where you past the cyclic lists. Can you do an example for

\{(1,2,3), (4,5,6)\}

? (where I've arbitrarily cut the list like David)

Morgan Rogers (he/him) (Feb 06 2023 at 09:54):

Based on the construction @Ben Sprott described, I think the result would be

(1,2,3,4,5,6,1,2,3,5,6,4,1,2,3,6,4,5, 2,3,1,4,5,6,2,3,1,5,6,4,2,3,1,6,4,5, 3,1,2,4,5,6,3,1,2,5,6,4,3,1,2,6,4,5)

@Ralph Sarkis; let's see if this is well-defined, which requires an alternative choice of orientation of the lists to produce the same result up to orientation. By construction, rotating the first list by 1 corresponds to rotating this list by 18, so that's good. Rotating the second list by 1 should correspond to rotating the result by 6, but then the numbers coming from the first list fail to rotate properly. The same problem arises for rotating the outer list...
To be well-defined, we would need all of the possible choices to appear symmetrically, which means that if the original lists have length

n_1,\dotsc,n_m

and the new list has length

N

, we need an injective group homomorphism

C_m \times C_{n_1} \times \cdots \times C_{n_m} \to C_N

. But such a group homomorphism does not exist in general, since by the Chinese remainder theorem

C_N \cong C_{p_1^{k_1}} \times \cdots \times C_{p_l^{k_l}}

where

N = p_1^{k_1} \cdots p_l^{k_l}

is the prime factorization of

N

, and so if

n_i,n_j

have a common prime factor

p

for

i \neq j

we need the group homomorphism to embed

C_p \times C_p

into

C_{p^k}

for some

k

, which is not possible.

Morgan Rogers (he/him) (Feb 06 2023 at 09:56):

Morgan Rogers (he/him) (Feb 06 2023 at 10:01):

One way to fix this is to instead take "multicyclic lists", where you have an

n_1 \times \cdots \times n_m

matrix of elements from your set, and allow cyclic permutations in each dimension (I am proposing this here and now, not pointing to an established concept I am aware of). The multiplication will be some kind of "tensoring" of such matrices, although the exact details would require me to sink a lot more time into this, so I'll let you run with it.

Ralph Sarkis (Feb 06 2023 at 10:29):

David Michael Roberts (Feb 06 2023 at 23:45):

One thing I would warn here is that Ben seems to have a specific mental picture involving data arising from experiments, and shopping around to invent a monad (or similar) that's vaguely reminiscent or uses similar jargon may be counterproductive. And, not to put too fine a point on it, this kind of thing had already been happening before this discussion, for a number of rounds.

dusko (Feb 07 2023 at 04:50):

does it help to remember that monads are presentations of algebraic theories? if

{\cal L}_C

is a monad, then there must be an algebraic theory (possibly infinitary) such that

{\cal L}_C X

is the free algebra over

X

. if cyclic lists are based on cyclic graphs as above, then they are surely not a category of algebras, since they would be a variety in graphs, and a subgraph of a cyclic graph needn't be cyclic. (intuitively, to say "cyclic" i need an existential quantifier. goodbye equational presentation.)

Ben Sprott (Feb 08 2023 at 20:57):

@David Michael Roberts has tried in the past, and again here, to have me define things better. I understand his sentiment, and it may be playing out here. There seems to be a few proofs under way that people have done here to show that cyclic list is not a monad. This is important to know, obviously. The definitions that David asked me to confirm all correctly agree with my understanding. There may be some other definition of the product nat-trans that makes it a monad, but I am at a loss. I had to ask. There is no intuition that I have that suggests a different one.

My interest in monad structure is from a scientific perspective, in that the product axiom performs the act of amalgamating data. If you've read Spivak's science text book, you see how he does this with spans. A multiset of multisets amalgamates all the data by dissolving the inner bags.

At the risk of confirming David's criticism that this is a fishing expedition, I am now going to suggest the way that I resolve this kind of dilemma in other instances of my work. I will now embark on the goal of showing that cyclic list is a comonad.

In the end, I need some kind of (co)monad that will give a category of convex spaces that are (bi)algebras by the Eilenberg-moore category.

John Baez (Feb 08 2023 at 21:09):

John Baez (Feb 08 2023 at 21:29):

Anyway, there's a monad whose Eilenberg-Moore category is a category of convex spaces. See the first section of [[convex spaces]] on the nLab.

Ben Sprott (Feb 09 2023 at 04:12):

Abstract. We propose an abstract definition of convex spaces as sets where
one can take convex combinations in a consistent way. A priori, a convex
space is an algebra over a finitary version of the Giry monad.

I think of EM categories over a measures monad as a category of convex spaces. I don't know if this is a good way to think of these thigns.

Did you see my preprint? . It's only a few pages. It would an honour if you read it. Do you want to talk about this idea of mine and see if we can poke a really big hole in it? I am claiming to have formulated a way to compute the correct form of quantum theory for a successful theory of quantum gravity. It is similar to the information theoretic derivations of QM, except it uses symmetries of data, which I see as more fundamental than information. I work in the ecosystem of monads on Set. Furthermore, I believe I may have a way to compute an actual theory of quantum gravity using all these techniques. I believe the reason no one has done it is because the math is too hard and not figured out yet.

John Baez (Feb 09 2023 at 04:39):

Sorry, I don't want to talk about quantum gravity - I quit working on quantum gravity in 2005 and have been happier ever since I stopped thinking about it or talking about it. I was just hoping you'd answer my question: you suddenly jumped from talking about cyclic lists (which are almost certainly not algebras of a monad on Set) to convex sets (which are), so I asked "what do cyclic lists have to do with convex spaces"? If the answer is related to your ideas on quantum gravity then okay, that's fine.

John Baez (Feb 09 2023 at 04:40):

You don't need to rely on Tobias' paper to know that [[convex spaces]] as usually defined are algebras of a monad on Set; I added some references to the nLab page [[convex spaces]] to papers that prove this is true. (I've worked a bunch with convex spaces, and I needed to learn about this stuff.)

Ben Sprott (Feb 09 2023 at 05:44):

So, we get a category of convex spaces from the EM construction on the distribution monad (finite giry monad). That's exciting. My gag is to compose the cyclic list (co?) monad (it doesn't look like a monad at this point) with the mulstiset monad. My guess was that if you compose the cyclic list monad with the multiset monad, you get another monad (given a distributive law) and hence via EM construction a category of convex spaces akin to Hilbert spaces. So, I do this to derive a form of quantum theory.

I guess, while I have you on the line, let me ask you this. Suppose we find that cyclic lists is a comonad. Then suppose we find a distributive law that allows for a composite that gives the cyclic lists of multisets (co)monad (bimonad). (edit: there was a mistake here, you need to pull off a monoidal move to map the multiset monad to the distribution monad. Then you have cyclic lists of distributions) This should give a category of bialgebras under the EM construction, but I would also consider this a category of convex spaces (I am guessing) right? That is, unless comoands, under EM construction, give a category of some kind of dual spaces (concave? LOL) . And then what do you call the spaces in the EM construction of a bimonad (which I sometimes call (co)moands)?

My interest in categories of "convext spaces" comes from an abiding interest in deriving quantum theory from simiple axioms, or some simple methods. My former advisor Lucien Hardy and also Chiribelli work to do this in different ways, but I do it differently. The preprint is not about quantum gravity. It is a derivation of a form of quantum theory. You could look at it that way. Really, though, you should take an interest in my work because I am constatnly showing that there is good reason to do applied math in the ecosystem of (co)monads on Set. Spivak is working in the ecosystem of polynomial endofunctors on set. I just like to add monad structure, because I believe it always gives a doorway to categories of algebras like Hilbert spaces via the Eilenber-Moore construction. I learned about algebras over an endofunctor.

Maybe you would prefer to talk about how I am applying all this math to artificial intelligence. I am running a startup where the core AI is designed in category theory.

Ben Sprott (Feb 09 2023 at 06:12):

John Baez (Feb 09 2023 at 06:18):

John Baez (Feb 09 2023 at 06:23):

This seems quite unlikely to me, so if I were studying this I wouldn't base any plans on it: I'd just prove or (more likely) disprove this before proceeding.

No, that doesn't sound right at all. I don't think you can get anything like convex spaces out of cyclic lists or multisets.

I think I'll quit here, just giving you my warning that none of these plans seem likely to work. They just don't make sense to me.

John Baez (Feb 09 2023 at 06:25):

It might work better to apply artificial inteligence to this math. :upside_down:

Ben Sprott (Feb 09 2023 at 06:41):

Well, John's out. We all know that's a stern warning to anyone toying with the idea of getting involved. Still, the questions are fairly well phrased. Is cyclic lists a monad? No. Ok fine. Is it a co-monad? Maybe, but not likely. It's all part of the effort when working in the ecosystem of monads on Set. And that's what I do for a hobby. It's nothing terribly pathological. I guess I'm back to math overflow.

I will just say that John was a bit rough there at the end but I have the absolute best researchers on contract at the startup. Using Category Theory has been very successful for getting ahead and sharing ideas. No need to apply AI to the math :big_smile::big_smile:.

David Michael Roberts (Feb 09 2023 at 06:48):

Before you try to prove the free cyclic list functor is a comonad, with the aim of somehow composing it with a monad, maybe check if it's even possible to do such a composition. This is where category theory is in its element: you can rule out certain avenues of enquiry on formal grounds, rather than messing around with a certain example.

Ben Sprott (Feb 09 2023 at 06:52):

Ralph Sarkis (Feb 09 2023 at 07:08):

A difficulty comes up very quickly when trying to prove

L_C

is a comonad. How to define the counit? You need to define a function

L_C X \to X

that sends a cyclic list over

X

to an element of

X

. I really don't see how to do that without making "unnatural" choices. If

X

had an additional structure, like an associative commutative binary operation on it, then you could use that to combine all the elements in the cyclic lists.

Like John, I believe you are mistaken. A category of EM algebras for a monad is a category of algebraic objects (hence the name). For the particular example of probability monads, we indentified the EM algebras with convex spaces, but that is a very special case. Maybe you don't have to deal with a (co)monad in your application. There are algebras for plain endofunctors.

Morgan Rogers (he/him) (Feb 09 2023 at 07:09):

To answer the direct question, there isn't a natural way to select an element from a cyclic list (they all have equal status!), so you have little hope of constructing a counit map to present this as a comonad.

I can see that David and John have been put off by the fact that you seem to be overextending your "intuition from physics". Convex spaces are an example of algebras for a monad, it's true, but this is by no means a generic example. Algebras for a monad more typically behave like, well, algebras, which only rarely can usefully be thought of as spaces.

Morgan Rogers (he/him) (Feb 09 2023 at 07:10):

John Baez (Feb 09 2023 at 07:17):

Nice argument, Ralph. So yes, the functor

L_C : \mathsf{Set} \to \mathsf{Set}

, sending any set

X

to the set of cyclic lists of elements of

X

, cannot be made into a comonad in any way, because there is no natural transformation that could serve as a counit.

John Baez (Feb 09 2023 at 07:20):

I'm repeating this only because Ralph said "I really don't see how to..." and Morgan said "you have little hope", which might lead a optimist to think there was still a chance.

Ben Sprott (Feb 09 2023 at 07:21):

I can see that David and John have been put off by the fact that you seem to be overextending your "intuition from physics". Convex spaces are an example of algebras for a monad, it's true, but this is by no means a *generic* example. Algebras for a monad more typically behave like, well, algebras, which only rarely can usefully be thought of as spaces.

I think the focus on convex spaces is not helpful. Really, the hypothesis from this physicist is that we design something using (co)monads on set and we expect to get a category of algebras (the language is going to be a problem here too) using EM. Furthermore, what we design is about data, something quite naturally central to science. The big mistake I made years ago was not to doggedly show if cyclic list is a monad.

Ben Sprott (Feb 09 2023 at 07:24):

David Michael Roberts (Feb 09 2023 at 07:25):

@Ben Sprott I see a paper by Power and Watanabe (you didn't link to a specific paper, but that's the one I looked at), where they list six different ways of combining monads and comonads. At this point, if you don't have a concrete construction in mind that you are trying to identify as coming from a category theoretic construction, and are just hoping that one of these will turn out to give you some physics (say) and you are taking a stab in the dark as to which one, then I would seriously think about the underlying methodology here. It would be far better to try to figure out what your theory is, without using category theoretic language at all, and then try to identify the structure you have, than start with some objects and a vague idea they should do something and hunt for a CT-theoretic construction, any CT-theoretic construction, with some variation on jargon in the name (maybe the idea is not vague in your mind, but I've not seen enough details yet to have more than a vague idea, and that includes the preprint linked above).

You can do the mathematics here without categories, (co)monads etc, but you can't do the categories, (co)monads etc without the mathematics.

David Michael Roberts (Feb 09 2023 at 07:27):

This is the issue. It seems like it was a bunch of super-generic ideas that felt like a solution in search of a problem.

Ben Sprott (Feb 09 2023 at 07:33):

I am trying to do some cool things with the monoidal structure on the category of monads on Set. I give details in the paper and the beginning of it are in the post above listed with an edit. Take a look at that monoidal move. It might be interesting to discuss. The idea is, can you do familiar monoidal moves given a distributive law?

Ben Sprott (Feb 09 2023 at 07:36):

Morgan Rogers (he/him) (Feb 09 2023 at 07:40):

What is "the monoidal structure on the category of monads on Set" that you refer to?

Morgan Rogers (he/him) (Feb 09 2023 at 07:42):

Ben Sprott (Feb 09 2023 at 07:42):

Ben Sprott (Feb 09 2023 at 07:54):

I mean, the long and short of it is that this is what I want to do, guys. These are the tools I want to use.

I want someone to make an industry in academia of applied mathematics with the category theory tools I am using: category, functor, monad, comonad, kleisli category, EM category, monad composition, monoidal moves. If you are wondering if it's a good bet, just look at what Bart Jacobs has been up to. Imagine if his progeny had all these tools to work with. Composition is known to be a good tool to build up structure. We don't have it in monads because it's hard, so let's fix it so it's not so hard.

I just hope that the applications to quantum, probably and AI that I am trying to demonstrate are compelling.

Morgan Rogers (he/him) (Feb 09 2023 at 07:59):

Is that someone you? They use strikingly similar language. At any rate, it doesn't seem like they found a neat description of composition of monads via distributive laws as a monoidal product, and it seems pretty misleading (rather than "interesting") to talk about "the monoidal structure" when that structure may not be well-defined. This is not the first time in this discussion that you have talked about structure that you haven't actually checked the existence of for yourself.

I appreciate the sentiment of wanting to apply category theory, but the truth is that you can't apply theory unless you have a solid understanding of it. To paraphrase what David said, guessing at things that might work and hoping that they turn out to be good ideas is not a realistic strategy for applying category theory.

Ben Sprott (Feb 09 2023 at 08:33):

It looks like Morgan is out. He's actually saying that what I am doing is unethical. Make your choices as to whether to keep reading my posts, I guess. Maybe he's right. I guess if you read my papers and assumed I checked everything, you would be fooled into thinking there's something there when there isn't. I certainly never hoped that would happen. My intention has never been to project an image of myself as a successful and talented applied mathematician. It's just to encourage people to consider what I am saying, and, if they have time, check it themselves.

Again, really, it is straightforward. I am just looking for someone to answer a question. Really, to engage with me. In this case, the question is, given a monad composition and a monad map applying to one of the composites, can I apply it tensored with an identity like a monoidal move? Nothing pathological. Just a really good question.

David Michael Roberts (Feb 09 2023 at 08:53):

Please give a complete and rigorous definition of a "monoidal move", and not by pointing to an external source if possible.

And I humbly note that this was not in the question asked, but details about a specific putative but non-existent monad, and then a putative and then non-existent comonad. The goalposts keep shifting, and mentions of applications that so far I've not seen. I'd love to see applications, but if in the past two years my question on MO about the full definition of the cyclic lists endofunctor was not answered (I'm assuming this, because it wasn’t given here, and I supplied it by guessing), I do wonder what actual details of these applications have been figured out in the meantime. You mentioned a start-up: perhaps it's not there yet, but what concrete thing has it produced, if it is?

David Michael Roberts (Feb 09 2023 at 09:05):

I'm being pedantic here because if the product is supposed to be tools based on category theory, my confidence is not bolstered by what seems, based purely on this conversation, like a relaxed attitude to checking basic definitions hold. This is not proving something like the category Poly has, what, five monoidal structures, interacting in complex ways and that data migration models are an instance of what is happening here. It's writing down the definition of a single endofunctor and doing some concrete checks with concrete small examples as to whether a hoped-for structure is possible. And as soon as one structure is ruled out, being happy to just use the next one in the bag, with no apparent worry that this wholly changes the nature of the structure being applied....this worries me.

Ben Sprott (Feb 09 2023 at 09:42):

This is interesting. I actually need the monad to be higher dimensional to fit my model. It's right at the bottom of my paper. This might work for me. I will put it up on math overflow to set if anyone can complete it. Thank you.

Morgan Rogers (he/him) (Feb 09 2023 at 09:45):

Do the work yourself! Why should other people do your working out for you? How will you know that an answer they give is valid if you are making no effort to develop your own understanding of the concepts you're trying to work with?

David Michael Roberts (Feb 09 2023 at 11:22):

Jules Hedges (Feb 09 2023 at 12:05):

I never thought about it before but I was quite surprised to convince myself that circular lists arrange into neither a monad or a comonad, since circular lists are a really important data structure that every programmer knows. On the other hand, "pointed circular lists" (aka circular lists equipped with a handle to one element designated "first") I'm pretty sure will arrange into a comonad, namely a sub-comonad of the stream comonad. There's a more general data structure "eventually cyclic lists" - aka lists that can point back somewhere into themselves - aka "infinite streams that can be represented with only finitely many nodes" - aka "rational lists" that behave like the decimal expansion of a rational number, which is eventually periodic. They have some quite nice associated category theory, that was studied by Conor McBride

Spencer Breiner (Feb 09 2023 at 12:40):

Jules Hedges (Feb 09 2023 at 12:50):

A cyclic list contains one additional piece of information, namely the "last" element can (optionally) contain a pointer back to somewhere inside the list. The notion of equality is also a bit more subtle, eg. you have equations such as

0\overline{12} = 0\overline{1212}

Spencer Breiner (Feb 09 2023 at 12:50):

Spencer Breiner (Feb 09 2023 at 12:51):

David Michael Roberts (Feb 09 2023 at 12:56):

@Jules Hedges I'm not sure that's what Ben means, since as far as I can tell he's thinking of a list that's arranged in a circle.

Morgan Rogers (he/him) (Feb 09 2023 at 13:07):

I also had interpreted "cyclic lists" to mean "lists modulo cyclic permutation" in my responses above.

Ben Sprott (Feb 09 2023 at 17:46):

I want to apologize to the forum. I believe I understand what has happened, and I agree its my fault. As an entrpreneur, it is your job to take risks and then get people to buy into those risks in order to ensure that the risks go away with their input and a path to success is achieved. So, I am now doing that with my science projects. I am making claims to get people interested and it is crossing the line. I get it. You need me to do more work myself, I am sorry but I can't. The problem is that I am making claims that make it really sound like I have verified all this, when I haven't and I apologize for that.

Furthermore, this bears out in technical terms by my saying "hey guys, let's do a composite of monads" when, in fact, I did not successfully prove that I even had monads. I apologize for that. I will add one embarassing thing. I had actually forgotten that I did not prove cyclic list was a monad. I had completely forgetten this and then just lived in a world where it was settled. Ughh.

Ben Sprott (Feb 09 2023 at 17:54):

I want to clean up what happened with John about convex spaces. The problem was that I was not focusing and giving the exact story and really thinking as John asked his questions. My mistake for him was to tell him that I believed that cyclic lists of multisets would have an EM category of convex spaces. I don't (really) believe that and I never have.. I simply belive that a monad of normalized meausures gives an EM category of convex spaces. So how do we get to a monad of normalized measures from cyclic lists of multisets? This is where the "monoidal moves" come in, and yes, there is no canonical monoidal product, but there is a glimmer of hope that if you have a distributive law, then you can do something that looks like monoidal moves. This needs to be verified. Specifically, what I am interested in is this move:

Where we are mapping just one of the parts of the composite, namely, we are mapping multisets to distributions to get cyclic lists of distributions. Supposing this works and forms a monad, will this have an EM category of convex spaces? Probably not. So, what then? Well, we are going to try to use our intution about the converting of hilbert vectors to probabilities in order to say, ok, how do we map cyclic lists of distributions to a monad of just distributions. This is something I don't know how to do.

Joshua Meyers (Feb 09 2023 at 18:15):

I agree that a monad of normalized measures gives an EM category of convex spaces!

It would help me a lot with understanding what you're asking next if you defined the following symbols:

Maybe I am being obtuse and I should be able to figure it out from context, but I am trying to do so and I am not having much luck. Could you please state what these symbols mean?

John Baez (Feb 09 2023 at 18:35):

You haven't even said what a "cyclic list" is. We've seen people in this thread scratching their heads, making up different definitions of "cyclic list", in an attempt to figure out what you're talking about. You've never said which definition you mean. What's a "cyclic list"?

Jules Hedges (Feb 09 2023 at 19:00):

Cyclic lists (I say circular lists) are a standard thing in computer science, it means (in mathematical terminology) an equivalence class of lists modulo list rotation, ie. if you remove an element from the start and put it on the end then the result is equal. (Any definition of cyclic lists that's not equivalent to that would be wrong)
https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature

Joshua Meyers (Feb 09 2023 at 19:09):

@David Michael Roberts above gave a pretty nice definition of "cyclic list functor", --- @Ben Sprott should confirm that this is what he is talking about, deny that this is what he is talking about, or ask for clarification on the definition.

David Michael Roberts (Feb 09 2023 at 21:45):

What exactly is the "this", and what endofunctor is meant to be part of a monad?

David Michael Roberts (Feb 09 2023 at 22:10):

To give a constructive suggestion, and I was already thinking this last night, but we had a plumbing emergency: @Ben Sprott, you should get in the habit of rigorously documenting the mathematics you are doing. I felt frustrated trying read the temporarily linked preprint, as it claimed to give definitions, but then just waved the reader on past with an example that was insufficient to even convey what was going on. It claimed to define "the cyclic lists monad", giving the vague recipe mentioned earlier this thread. But it didn't define the underlying endofunctor, nor did it prove the required conditions.

Building up a master document, which doesn't have to be public, with all the things you know, and clearly labelling conjectures as such, and referencing matters with rigour, is an absolute must. When you asked about the cyclic lists endofunctor on MO back when, you pointed vaguely to a big paper of Joachim Kock. If you point to definition/proposition/theorem numbers it helps to cross-reference and double check. And in that instance, Kock was talking about an endofunctor of the category, or possibly 2-category, of groupoids. But you have meant all this time an endofunctor on Set. Not to mention, his definition was implicit, as a polynomial endofunctor defined via an arrow of Gpd, whereas you were thinking of...something else. So, actually proving your own definition and someone else's that is presented in a different way are in fact the same is a necessary step, if you are claiming to use their work. And the proof needs writing out in detail.

David Michael Roberts (Feb 09 2023 at 22:16):

This way, you have documentation that means you can check what you have actually done, what you only currently hope is true, and so on. This will give you practice in doing category theory, and I think working through Tom Leinster's textbook (available on the arXiv), and doing all the exercises in detail, will be useful. And maybe in parallel, or after that, Emily Riehl's. There's no royal road to geometry, and no royal road to category theory, either. The exercises can seem a little bit trivial, until suddenly they aren't, so it's important to keep doing them.

John Baez (Feb 09 2023 at 22:36):

I was wondering what Ben thought a cyclic list was, since he was the one who started talking about them.

David Michael Roberts (Feb 09 2023 at 23:02):

I think the first description is not what he meant, but the descriptions after the 'i.e.', which agrees with Jules most recent definition (as opposed to the 'eventually cyclic' lists earlier).

John Baez (Feb 09 2023 at 23:08):

I would have other questions for Ben, but it looks like other people are so eager to answer that there's no point. Here David pointed to two different answers from Ben... and then went ahead and chose one for him!

Dan Marsden (Feb 12 2023 at 15:57):

I may have missed some (a lot of!) posts here, so if this misses the point I apologise in advance. There is a non-empty cyclic list comonad C on the category of sets and functions. The non-emptiness is important for the counit to be well defined. C(X) is non-empty lists of elements of X. The counit takes the head of a list, and the comultiplication takes a lists to it's list of "sublists", wrapping around in a cyclic manner. So for example [1,2,3] goes to [[1,2,3],[2,3,1],[3,1,2]]. This appears in "When is a container a comonad" and is credited to Jeremy Gibbons. In particular, the notion of circular list here is not an equivalence class of lists, but a non-empty list which "loops around" in terms of the sublist at a given position. The previously proposed equivalence classes up to list rotation seems problematic to me, as you have lost information. Where is the "front" of the list? I can't see how this mathematical description captures an intuitive data structure?

Morgan Rogers (he/him) (Feb 12 2023 at 20:08):

Dan Marsden (Feb 12 2023 at 21:29):

I agree for a "topological" cycle, there's no meaningful front, but if I understood the context, it was as a data structure. The Gibbons style cyclic list has a front, or probably "focus element" would be a better term, and a notion of next element. The next element operation cycles through the positions in the list. In a conventional list [1,2,3], the remaining list at the second position is [2,3], whereas for a cyclic list it is [2,3,1]. So the cyclic lists can also be through of as a subcomonad of the stream comonad restricted to periodic streams (I think this is obvious). On the other hand, a collection of lists up to rotation doesn't seem in any simple sense to model a natural data structure, at least as far as I can see, as how would you interact with the "collection" of data? It does on the other hand capture cycles in the topological sense you suggest. So it could be that I'm simply muddling up what was being discussed, as I jumped in rather late! Certainly though, the Gibbon's style cyclic list is a natural definition, and it doesn't coincide with that is encoded by rotation equivalence classes of lists.

David Michael Roberts (Feb 13 2023 at 01:02):

I think @Ben Sprott really needs to clarify here and/or to confirm people's guesses as to what he means.

The problem is not finding any old (co)monad in approximately the right neighbourhood of lists (I'm strongly discouraging this approach), but there's a mental model about data coming from experiments that Ben has, and my impression the goal is trying to see if that specific idea is encodable using some of kind of monad.

Ben Sprott (Feb 14 2023 at 00:20):

I'm sorry for causing this mess guys. Not only did I not prove that cyclic list is a monad. I didn't even define the functor, at least not in any rigorous way. I thought it was self evident. The definition that one would make in computer science is a finite list where every element points to one other element. Recall that a list is a sequence, ie it has an order. This forms a circle of pointers or references and it can be seen as a directed graph that forms a circle. Is this not enough to have a rigorous definition? I was surprised to see Morgan write a flat list with repeating sequences of elements, but that might be closer to the truth. They are the same thing in some sense, but it may be hard to define exactly how they are the same thing.

Ben Sprott (Feb 14 2023 at 00:59):

Everyone here is trying to get me to give a precise definition of what I mean by cyclic list. I think your definition is acceptable but I never really liked the idea of having a focus or start element. I am trying to model real data, so for sure there is a start element. I am imagining an experiment where someone starts copying down numbers, emphasis on starts.

I think it's important for the broader math community, especially the great people in this forum, to learn about the work done on containers which is more known in computer science.

David Michael Roberts (Feb 14 2023 at 01:17):

What about the list {1,2,3,4,5} with the pointers 1-> 2 -> 1, 3 -> 4 -> 5 -> 3? {Edit: I meant the list [1,2,3,4,5], not the set]
Or the list {1,2,3,4} with pointers 1 -> 2 -> 3 -> 4 -> 2? [Edit: ditto here, it is the list [1,2,3,4]}

I know you mean 1 -> 2 -> 3 -> 4 -> 5 -> 1, but this is not what your definition says, and both of the above are possible. You don't need a totally formal definition at the level of set theory, or whatever, but just saying something like "a cyclic list is a single-cycle directed graph where the nodes are decorated with elements from a set" is enough. Does your definition have a specified element in these sense that it's a bona fide list, together with a cyclic ordering? Or there is no starting element? People here might be genuinely misunderstanding what you mean, but also are trying to bring their own understanding to an underspecified construct.

David Michael Roberts (Feb 14 2023 at 01:18):

and this was not what I thought you meant, so I'm in the crowd of people who misunderstood what you were trying to say. I assumed you meant there was no starting element, and only the data of a cycle.

David Michael Roberts (Feb 14 2023 at 01:18):

So not only was the functor not defined, the very definition of cyclic list was underspecified, and people have been proving things about definitions of cyclic lists that may or may not be what you were thinking about.

David Michael Roberts (Feb 14 2023 at 01:23):

in this case, why do you need the cyclic business? Is this just a stream? Or are you really interested in the writer monad ?

This is why it's important to document your ideas thoroughly and completely, leaving as few details out as possible, keeping enough so someone who doesn't have recourse to ask clarifying questions over time can understand exactly what you mean.

Ben Sprott (Feb 14 2023 at 01:48):

I think you made a mistake, so correct me if I don't have this right. You have a "list"
as {1,2,3,4,5}. This looks like a set because of the curly braces and the fact that everything is unique. Here is a list [1,2,3,4,5,2,4]. Recall that a list is ordered, so everything in this list is understood to point at the thing next to it. In your notation that looks like this:

Notice how everything points to one other thing except for one element, the last one, 4. To turn this into a cyclic list, we just add one last pointer from the end to the beginning. This is why I chose the clever definition "a list where every element points to one other element", perhaps we want to say "a list where the last element points to the first element".

David Michael Roberts (Feb 14 2023 at 02:07):

@Ben Sprott Ignore the braces there, that is purely cosmetic. Read it as a list [1,2,3,4,5], with the pointers 1-> 2 -> 1, 3 -> 4 -> 5 -> 3. In this example I have a list and each element is pointed to one other element, which is the definition you gave.

Ben Sprott (Feb 14 2023 at 02:08):

David Michael Roberts (Feb 14 2023 at 02:08):

I didn't understand that, as your definition merely said that each element points to one other element. It didn't say that this pointer needed to point to the next element in the list, except the last element.

Ben Sprott (Feb 14 2023 at 02:09):

David Michael Roberts (Feb 14 2023 at 02:10):

You are defining "cyclic list", and so you can't say my example of your definition is wrong if you then say oh, that's a "cyclic list with a tail". What's a "cyclic list with a tail", then?

Ben Sprott (Feb 14 2023 at 02:29):

I was being sarcastic when I said clever. It's not clever and it's wrong, as you are pointing out. What's wrong with "cyclic lists where the last "element" points at the first "element"."

David Michael Roberts (Feb 14 2023 at 02:55):

There's no problem with the word 'element' here (one might say 'entry', but it's not a problem). Defining a cyclic list

and each element points to the next element in the list is clear, now the issue is whether the given list structure is inherent to the structure, namely the data is a cyclic list is a list, with the understanding that the 'next' element after the last given element is the first element, or if there is no first element. Another way to think about this is that in the API for the cyclic list data structure, you cannot extract a first element. So there are two options:

David Michael Roberts (Feb 14 2023 at 02:55):

David Michael Roberts (Feb 14 2023 at 02:59):

[The important part of the above data structure is that one really does have a starting element, namely the head of the list at the start, and this is remembered forever. Perhaps my sketch of the implementation is a bit wonky, I hope it is clear. Perhaps you can supply a similar implementation of what you mean.]

David Michael Roberts (Feb 14 2023 at 03:01):

David Michael Roberts (Feb 14 2023 at 03:02):

David Michael Roberts (Feb 14 2023 at 03:11):

I mean: it is clear that you mean a single cycle, but whether the cycle should have a special chosen element that is the 'first' element, or not, is not yet established. This will be driven by what your intended application needs.

Joshua Meyers (Feb 14 2023 at 15:34):

I guess the question is whether [1,2,3,4] and [2,3,4,1] are the same cyclic list

Stream: theory: category theory

Topic: Monad composition

Ben Sprott (Feb 04 2023 at 17:24):

Ralph Sarkis (Feb 04 2023 at 19:06):

Ben Sprott (Feb 04 2023 at 19:45):

Ben Sprott (Feb 04 2023 at 19:46):

David Michael Roberts (Feb 05 2023 at 01:49):

Ben Sprott (Feb 05 2023 at 18:51):

Ralph Sarkis (Feb 05 2023 at 19:28):

Ben Sprott (Feb 05 2023 at 20:46):

Ben Sprott (Feb 05 2023 at 20:50):

Ben Sprott (Feb 05 2023 at 21:35):

David Michael Roberts (Feb 05 2023 at 22:09):

David Michael Roberts (Feb 05 2023 at 23:57):

David Michael Roberts (Feb 06 2023 at 00:02):

Ralph Sarkis (Feb 06 2023 at 08:26):

Ralph Sarkis (Feb 06 2023 at 08:28):

Morgan Rogers (he/him) (Feb 06 2023 at 09:54):

Morgan Rogers (he/him) (Feb 06 2023 at 09:56):

Morgan Rogers (he/him) (Feb 06 2023 at 10:01):

Ralph Sarkis (Feb 06 2023 at 10:29):

David Michael Roberts (Feb 06 2023 at 23:45):

dusko (Feb 07 2023 at 04:50):

Ben Sprott (Feb 08 2023 at 20:57):

John Baez (Feb 08 2023 at 21:09):

John Baez (Feb 08 2023 at 21:29):

Ben Sprott (Feb 09 2023 at 04:12):

John Baez (Feb 09 2023 at 04:39):

John Baez (Feb 09 2023 at 04:40):

Ben Sprott (Feb 09 2023 at 05:44):

Ben Sprott (Feb 09 2023 at 06:12):

John Baez (Feb 09 2023 at 06:18):

John Baez (Feb 09 2023 at 06:23):

John Baez (Feb 09 2023 at 06:25):

Ben Sprott (Feb 09 2023 at 06:41):

David Michael Roberts (Feb 09 2023 at 06:48):

Ben Sprott (Feb 09 2023 at 06:52):

Ralph Sarkis (Feb 09 2023 at 07:08):

Morgan Rogers (he/him) (Feb 09 2023 at 07:09):

Morgan Rogers (he/him) (Feb 09 2023 at 07:10):

John Baez (Feb 09 2023 at 07:17):

John Baez (Feb 09 2023 at 07:20):

Ben Sprott (Feb 09 2023 at 07:21):

Ben Sprott (Feb 09 2023 at 07:24):

David Michael Roberts (Feb 09 2023 at 07:25):

David Michael Roberts (Feb 09 2023 at 07:27):

Ben Sprott (Feb 09 2023 at 07:33):

Ben Sprott (Feb 09 2023 at 07:36):

Morgan Rogers (he/him) (Feb 09 2023 at 07:40):

Morgan Rogers (he/him) (Feb 09 2023 at 07:42):

Ben Sprott (Feb 09 2023 at 07:42):

Ben Sprott (Feb 09 2023 at 07:54):

Morgan Rogers (he/him) (Feb 09 2023 at 07:59):

Ben Sprott (Feb 09 2023 at 08:33):

David Michael Roberts (Feb 09 2023 at 08:53):

David Michael Roberts (Feb 09 2023 at 09:05):

Ben Sprott (Feb 09 2023 at 09:42):

Morgan Rogers (he/him) (Feb 09 2023 at 09:45):

David Michael Roberts (Feb 09 2023 at 11:22):

Jules Hedges (Feb 09 2023 at 12:05):

Spencer Breiner (Feb 09 2023 at 12:40):

Jules Hedges (Feb 09 2023 at 12:50):

Spencer Breiner (Feb 09 2023 at 12:50):

Spencer Breiner (Feb 09 2023 at 12:51):

David Michael Roberts (Feb 09 2023 at 12:56):

Morgan Rogers (he/him) (Feb 09 2023 at 13:07):

Ben Sprott (Feb 09 2023 at 17:46):

Ben Sprott (Feb 09 2023 at 17:54):

Joshua Meyers (Feb 09 2023 at 18:15):

John Baez (Feb 09 2023 at 18:35):

Jules Hedges (Feb 09 2023 at 19:00):

Joshua Meyers (Feb 09 2023 at 19:09):

David Michael Roberts (Feb 09 2023 at 21:45):

David Michael Roberts (Feb 09 2023 at 22:10):

David Michael Roberts (Feb 09 2023 at 22:16):

John Baez (Feb 09 2023 at 22:36):

David Michael Roberts (Feb 09 2023 at 23:02):

John Baez (Feb 09 2023 at 23:08):

Dan Marsden (Feb 12 2023 at 15:57):

Morgan Rogers (he/him) (Feb 12 2023 at 20:08):