`topSort` doesn't know that the result of `scc` has no cycles

[michaelpj]

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.

[snowleopard]

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!

[michaelpj]

All I can think of is adding a phantom type parameter to track acyclicity, but that seems very heavyweight for marginal benefit.

[snowleopard]

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.

[michaelpj]

Well, except presumably you want all combinations of those properties, so either you need type level sets or lots of parameters.

[subttle]

It might be worth looking into linear types for this area.

[snowleopard]

@subttle I'm not sure how linear types can help. Could you clarify?

[subttle]

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

[chessai]

Two approaches that come to mind are refined and gdp for the phantom types approach.

[snowleopard]

@chessai Thanks, indeed!

Also, massiv is close in spirit: http://hackage.haskell.org/package/massiv-0.2.6.0/docs/Data-Massiv-Array.html