Higher-kinded Graph

[snowleopard]

There have been multiple discussions about making Graph higher-kinded, so I decided to create a separate issue for this -- let's discuss higher-kinded graphs here.

The key idea is:

class Monad g => Graph g where
    empty   :: g a
    overlay :: g a -> g a -> g a
    connect :: g a -> g a -> g a

vertex :: Graph g => a -> g a
vertex = pure

This is very nice from many points of view: we know that any graph is a monad, this leads to better type signatures, we can reuse fmap and do-notation, etc.

However, there is a big drawback: we lose non-fully-parametric instances, such as Relation, IntAdjacencyMap, and many others.

We could potentially have both versions in the library, with Algebra.Graph.HigherKinded dedicated to higher-kinded version of the Graph type class. I've already implemented this, see the commit below.

[snowleopard]

The good thing about this approach is that fully-parametric graph representations, such as, data Graph a can define both instances and therefore users can work with them using the most convenient interface.

Here is a snippet from Algebra.Graph.Data:

data Graph a = Empty
             | Vertex a
             | Overlay (Graph a) (Graph a)
             | Connect (Graph a) (Graph a)
             deriving (Foldable, Functor, Show, Traversable)

instance C.Graph (Graph a) where
    type Vertex (Graph a) = a
    empty   = Empty
    vertex  = Vertex
    overlay = Overlay
    connect = Connect

instance H.Graph Graph where
    empty   = Empty
    overlay = Overlay
    connect = Connect

[Gabriella439]

You can also add a stronger MonadPlus constraint to the Graph class, where mzero takes the role of empty and mplus takes the role of connect

[Gabriella439]

Oops, I meant that mplus takes the role of overlay. My understanding is that overlay is associative and empty is its identity

[snowleopard]

@Gabriel439 Interesting! I think formally, empty = mzero and overlay = mplus does satisfy all MonadPlus laws listed here: https://wiki.haskell.org/MonadPlus (apart from Left Catch, which seems to be a rather rare alternative to Left Distribution):

• mzero and mplus should form a monoid, and empty and overlay is a monoid.
• mzero >>= k = mzero translates to vertex substitution in the empty graph: empty >>= k = empty.
• mplus a b >>= k = mplus (a >>= k) (b >>= k) means: if we substitute vertices in an overlay a b we get the same result as if we substituted vertices separately in a and b and then overlaid the results.

However, we need to also make sure this makes sense semantically. As far as I understand, MonadPlus is used to represent alternatives, similar to the Alternative type class. But, as I mentioned before, overlay doesn't represent alternatives, which is emphasised by the decomposition axiom abc = ab + ac + bc.

This makes me think that although we formally could make MonadPlus a superclass of Graph, we shouldn't do that, because it doesn't make sense semantically and could therefore lead to confusion.

[l-d-s]

MonadPlus is also used for collections (see e.g. here).

I think the intention for type classes is that a given class has no semantics beyond its laws (and its relationship to other type classes). But I also suspect that overlay might turn out to have an "alternative"-ish meaning in some contexts.

[snowleopard]

@l-d-s Many thanks for the link! All ringad laws given in Fig. 1 hold when we define empty = mzero and overlay = mplus. There is also this interesting quote in the conclusions:

The laws that one should require for MonadPlus and MonadZero are a subject of great debate; arguably, one expects different laws for backtracking search, for nondeterministic enumeration, and for collections of results [...]

So, it looks like I'm wrong that MonadPlus semantically corresponds to choice.

I think the intention for type classes is that a given class has no semantics beyond its laws

Hmm, this sounds a bit unexpected to me, but this approach surely allows to maximise code reuse.

To sum up: I think I'm gradually getting convinced that higher-kinded graphs should be defined as:

class MonadPlus g => Graph g where
    connect :: g a -> g a -> g a

empty :: Graph g => g a
empty = mzero

vertex :: Graph g => a -> g a
vertex = pure

overlay :: Graph g => g a -> g a -> g a
overlay = mplus

With the above definitions we can reuse a couple of standard functions:

overlays :: Graph g => [g a] -> g a
overlays = msum

induce :: Graph g => (a -> Bool) -> g a -> g a
induce = mfilter

[snowleopard]

I just realised that we can make Relation an instance of higher-kinded graphs by postponing the actual evaluation which requires Ord a until we actually need it, say, to implement the Eq instance. This essentially means that we can turn pretty much all data structures into higher-kinded equivalents by hiding Data.Graph inside, which is used to build up fully parametric trees, and then at some point collapsing these trees into more efficient representations, on demand (perhaps, caching this somehow). This collapsing will require various constraints like Ord a, but it doesn't have to be at the Graph instance declaration.

[snowleopard]

The latest definition is:

class MonadPlus g => Graph g where
    connect :: g a -> g a -> g a

-- reuse empty from Alternative

vertex :: Graph g => a -> g a
vertex = pure

overlay :: Graph g => g a -> g a -> g a
overlay = (<|>)

If we are going this way, it may be useful to also make Foldable a superclass.

[snowleopard]

I've released the library with higher-kinded class available in the Algebra.Graph.HigherKinded.Class module: http://hackage.haskell.org/package/algebraic-graphs/docs/Algebra-Graph-HigherKinded-Class.html

[jmatsushita]

Hello there, I'm curious about whether this turned out to be false or if there is another reason why Relation doesn't have a H.Graph instance?

I just realised that we can make Relation an instance of higher-kinded graphs by postponing the actual evaluation which requires Ord a until we actually need it, say, to implement the Eq instance.

[snowleopard]

@jmatsushita I think the reason is that Relation isn't used much and so no one really wanted an instance of H.Graph. In fact, it's not clear we should keep Relation in the library since a few people remarked that it can be confusing to see so many different versions of more or less the same thing. (Perhaps, we could move it to a separate library algebraic-relations?)

By the way, once you start postponing the actual evaluation (which requires Ord a), you might as well switch to working with the algebraic data type (from Algebra.Graph) until the last moment you need to go to sets and start needing Ord a everywhere.

[jmatsushita]

Interesting thanks for letting me know! By the way my interest comes from having started to contribute to purescript-alga with the intention to play with graph comonads as described here http://blog.higher-order.com/blog/2016/04/02/a-comonad-of-graph-decompositions/

I might contribute back here if there's interest :) And maybe help move Relations in its own package too.

By the way, once you start postponing the actual evaluation (which requires Ord a), you might as well switch to working with the algebraic data type (from Algebra.Graph) until the last moment you need to go to sets and start needing Ord a everywhere.

I think I get what you mean, I'm not working with concrete graphs yet so I'm focusing on the type class hierarchy as I find it easier to reason about for now. I think I understand that it somewhat makes the computational complexity more opaque about but I'm willing to trade that off, I was wondering if it was even possible or if there was something I was missing :)

[snowleopard]

with the intention to play with graph comonads as described here

That's cool! I remember reading that blog post and thinking about how I could possibly make an efficient comonad instance for algebraic graphs. I never came up with anything but I hope you'll succeed where I failed!

I might contribute back here if there's interest :) And maybe help move Relations in its own package too.

Sure, that would be great!