search

iokasimov / apart

Get all your structure and rip it apart.
http://hackage.haskell.org/package/apart
BSD 3-Clause "New" or "Revised" License
30 stars 4 forks source link

Algebraic Graph structure #1

Open jmatsushita opened 3 years ago

jmatsushita commented 3 years ago

Hi there,

I've really liked your blog post on Apart and using Comonads as an abstraction for what is in memory and what is persisted. It's super clever and I'm still inspired by trying to use this more.

When I started looking at Data.Apart.Structures.Graph I was super excited since I really like alga but then after a while I started wondering whether we can describe arbitrary direct acyclic graphs with type Graph = Cofree Edges and I think the answer is no, but I wanted to check my reasoning with you. I think for instance you can't really build a -> b -> c without also adding an arrow between a and c which you might not want. Basically the problem, I think, is that Connect (in the alga definition) since it will want to connect all the previous vertices in the structure, to the new one you're just adding, will always connect probably more than you want. And since you don't have a way to remove edges, you can't really represent all graphs.

I think that seeing the base functor Edge as GraphOperations though might work? In this case we're really doing a bit of a event sourced version of the graph, where you can not only add vertices and edges, but also remove them. I'm not sure it would work with this algebraic construction though, and it certainly wouldn't be a simple as Cofree Edges. I came across this kind of construction using event sourced triples, with an assert/retract qualifier, but that's not algebraic and therefore doesn't guarantee that all your edges point to valid vertices.

Another way to look at it is that probably Cofree Edges actually describes some interesting subclass of Graphs that maybe have some Tree-ness to them? The fact that all recent Connect vertices will be connected to all previous vertices is interesting, maybe it's something like causality.

It would be fun creating an arbitrary instance for this and converting some randomly generated graphs into diagrams and see what comes out :)

I might be completely wrong here, so I'd be happy to learn more!

Cheers,

Jun

iokasimov commented 3 years ago

Hi @jmatsushita, you're absolutely right, I've tried to add other constructors to Edge which could connect to all previously defined vertices (with variations for connecting only the latest ones), but then this construction becomes too complicated for interpretation.

If we want to use operations to describe graphs, maybe Free fits better.