A comonad for graph decompositions

[bblfish]

Thanks for another great article. These are really helping me ground my intuitions in Category Theory and its application to programming. Btw. exploring co-monads does help shed a lot of light on what Monads are.

Since you are working with graphs, you may be interested in the semantic web which is based completely on graphs (and named graphs). The graphs need not be connected as they seem to have to be with Quiver. The key intuition one needs to develop there is one of semantics that stems from logic, ie notions of meaning and reference, etc... (it has many echoes in philosophy) . The aim there is to create a global distributed database on-top of the web. There are a couple of talks online on the banana-rdf wiki including one I gave in December 2014 at Scala eXchange, which develops a use case for the semantic web, with scala examples.

Since you are coming at this from a Category Theory perspective I think you will enjoy Benjamin Braatz's thesis "Formal Modelling and Application of Graph Transformations in the Resource Description Framework". I was trying to read this two years ago but got stuck at the time on pullbacks and pushouts, as I could not form a good intuition of those concepts. I think I should give it a shot again, as I feel I have a much better grip on CT now, after reading your articles, learning Haskell, etc. ... A later and easier to read 2010 paper of his might help motivate the category theory based approach "How to Modify on the Semantic Web? - A Web Application Architecture for Algebraic Graph Transformations on RDF" as it compares his theory to other standards such as SPARQL update. (To be honest I don't quite get the advantage of his position yet, but the parallels are very helpful).

Excellent illustrations by the way :-)

[jmatsushita]

Hi there, just a note for those who, like me just until a few minutes ago, where wondering if this exists in Haskell land: almost. Quiver is in fact based on fgl (as the Decomp and GDecomp give away) with small differences I can spot (like Decomp is done on an unlabelled Context) and a big difference which is that fgl doesn't have a (or rather neither of the) comonad instance(s).

But, of course, someone already pointed this out and with the code for a Comonad orphan instance.

[jmatsushita]

I wrote up a purescript implementation of the "all rotations" comonad as a PR for the purescript-fgl module https://github.com/amhuppert/purescript-fgl/pull/1

[bblfish]

@runarorama blog post has led recently to some enthusiastic thinking on comonads and the web.

Regarding my comment above from 5 years ago, I have since found one very nice explanation of RDF in the 2017 paper Knowledge Representation in Bicategories of Relations, which very helpfully places RDF in the space of bicategories rather than categories, that is where there are arrows between arrows too. But only 1 relation type: the sub property relation. That does not take away from the comonadic view of graphs presented in the blog post.

[bblfish]

I finally found the right way to describe RDF graphs which I wrote up in this Toot on mathstodon. As you will see this is why your blog post above with a description of nodes containing graphs was so interesting to me, as it seemed to capture exactly what was needed.

The new RDF Surfaces Community group uses a data structure where nodes can contain graphs. A paper gives some context called RDF Surfaces: Computer Says No. The idea is that with this construct, you can build first-order logic using ideas from Peirce. Searching around I found that the notion of graphs with graphs in the nodes goes back to at least 1990 with the paper The hypernode model and its associated query language whose abstract says:

"A data model called the hypernode model, whose single data structure is the hypernode, is introduced. Hypernodes are graphs whose node set can contain graphs, primitive nodes or literals. Hypernodes can be used to represent arbitrarily complex objects and can support the encapsulation of information to any level. A declarative logic-based language for the hypernode model is introduced and shown to be query complete. It is then shown that hypernodes can represent extensional functions, nested relations, and composite objects. Thus, the model is at least as expressive as the functional and nested relational database models. It is demonstrated that the hypernode model can be regarded as an object-oriented one."

I left many notes in discussion 280: Using scala-graph for RDF of the scala-graph project.

I think I will go for something similar to the quiver code but with a slightly simpler data structure. and perhaps a slightly different index.

Looking at the Quiver library, I was thinking the decomposition of a graph could be pretty expensive to do. Perhaps instead of decomposing the graph in your final example, you could just use what in banana-rdf we called a pointed graph, which was just a pair of a node and a graph. That way the graph only would need to be decomposed if needed.