search

snowleopard / alga

Algebraic graphs
MIT License
720 stars 69 forks source link

Higher-kinded `ToGraph`? #153

Open michaelpj opened 5 years ago

michaelpj commented 5 years ago

Seems like there are much the same considerations as for https://github.com/snowleopard/alga/issues/9. Again, I think the main driver would be getting rid of the type family.

We could have both, as we do for the Graph classes, but this is a bit annoying because of how many methods ToGraph has.

snowleopard commented 5 years ago

@michaelpj It's not technically difficult to add a higher-kinded version of ToGraph, but it feels wrong to maintain both versions. The same can be said about Class and HigherKinded.Class: I really would like to get rid of one of them (or both).

I think the main driver would be getting rid of the type family.

Could you expand this bit? Type families were introduced just for this very purpose: creating type classes for various collections (well, at least this one the main example using in papers on type families). They do require an extra extension and sometimes complicate the type inference, but isn't this an appropriate price for being able to handle not fully parametric instances?

michaelpj commented 5 years ago

I for one find it much easier to work with type parameters wherever I can. It feels strange to be using a type family when you are in fact parametric.

I guess I am probably biased by not caring so much about the non-parametric instances at the moment,

snowleopard commented 5 years ago

I've published a (rather long) blog post about one more type class that we might want to consider when working with algebraic graphs:

https://blogs.ncl.ac.uk/andreymokhov/united-monoids/

The type class United is not parameterised by vertex type at all: it captures only the notions of emptiness, overlaying and connecting things.

michaelpj commented 5 years ago

Looks nice - although in my case most of the things I'm working on really are very Graph-y, and wouldn't make much sense in a United setting.

snowleopard commented 5 years ago

What I meant to say is: perhaps we can switch to a graph type class that is not parameterised by the type of vertex, something like class United m => Graph m that comes with an additional law abc = ab + ac + bc on top of the laws from United. Then the dilemma (Class vs HigherKinded.Class) will evaporate.