search

snowleopard / alga

Algebraic graphs
MIT License
715 stars 68 forks source link

Monoid instance #269

Closed isovector closed 2 years ago

isovector commented 3 years ago

It seems to me that Graph is missing a Monoid instance:

mempty = empty
(<>) = overlay

There's also a monoid over connect, but that doesn't seem to be as relevant in terms of how people think about constructing graphs --- which is adding the vertices and edges to a bucket.

isovector commented 3 years ago

As an added benefit, it means empty could just be mempty and then wouldn't shadow the significantly more common Control.Applicative.empty.

snowleopard commented 3 years ago

I agree that overlay gives a more natural Monoid instance but I've never convinced myself that defining this instance is really worth it. Do you have a practical motivation?

As an added benefit, it means empty could just be mempty

I wouldn't want to remove empty from the API. (I find mempty ugly, sorry.) Anyway, it's easy to hide empty during import, so it doesn't seem like a strong motivation to me.

isovector commented 3 years ago

Yeah, hiding it is fine --- but without an alias like mempty, it's a challenge to subsequently use!

Though after spending a morning trying to drill interview problems, I'm not sure Algebra.Graph is what I'm looking for. I got confused by how many different graph representations there are, and how few of them I can do a dfs over.

snowleopard commented 3 years ago

Yeah, hiding it is fine --- but without an alias like mempty, it's a challenge to subsequently use!

If you hide empty you might still be able to use Control.Applicative.empty because there is an Alternative instance :)

Though after spending a morning trying to drill interview problems, I'm not sure Algebra.Graph is what I'm looking for. I got confused by how many different graph representations there are, and how few of them I can do a dfs over.

Yep, that's fair. I do want to kick a few graph representations out into a separate library to simplify this one. Functions like dfs are generally available via the ToGraph class, see ToGraph.dfs. I think all representations define suitable ToGraph instances, so you should be able to run DFS on any of them. Of course, performance will vary depending on the chosen representation.

ocharles commented 3 years ago

I would also like to see Monoid instance, as it opens up the ability to create a map using foldMap. I like to write things like:

myList & foldMap \Foo{ x, y, z } ->
   ... (vertex x) ... (edge y z)
snowleopard commented 3 years ago

Alright, let's add it then! To keep the API consistent, we'll need to add it to each of the zillion graph flavours in the library.

@ocharles @isovector Will either of you be interested in preparing a PR? If not, I'm happy to do it myself but I have a few other things to finish (e.g. reviewing and merging #274) before I'll get to it.