alga
alga copied to clipboard
snowleopard
`topSort` doesn't know that the result of `scc` has no cycles
A mild annoyance. Often you want to topologically sort your SCCs after condensing them. Indeed, part of the point is to get rid of cycles so your topological sort is well-defined!
But sadly topoSort doesn't know that we now have an acyclic graph, so still tells us the result might be Nothing.
This is indeed annoying, but I don't know how to nicely capture acyclicity in types.
We could provide a separate function for topSort . scc, with a fromJust behind the scenes, but that would be admitting the defeat.
Any ideas are welcome!
All I can think of is adding a phantom type parameter to track acyclicity, but that seems very heavyweight for marginal benefit.
Although heavyweight, phantom type parameters can bring other benefits too. We could use them for capturing all these graph variations in a uniform way:
- Acyclic vs cyclic
- Nonempty vs possibly empty
- Labelled vs unlabelled
- Directed vs undirected
- Reflexive, transitive, etc
So, in principle I'm ready to consider phantom types as a possible solution.
Well, except presumably you want all combinations of those properties, so either you need type level sets or lots of parameters.
Hm, when I actually work through what I had in mind it seems wayy more hacky than I thought it would be so I will say never mind for now and post back here if I figure out a way to do it nicer :P
Two approaches that come to mind are refined and gdp for the phantom types approach.
@chessai Thanks, indeed!
Also, massiv is close in spirit: http://hackage.haskell.org/package/massiv-0.2.6.0/docs/Data-Massiv-Array.html