New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
michaelpj opened this Issue Nov 30, 2018 · 9 comments

Comments

Projects
None yet
4 participants
@michaelpj
Copy link

michaelpj commented Nov 30, 2018

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.

@michaelpj michaelpj changed the title `topoSort` doesn't know that the result of `scc` has no cycles `topSort` doesn't know that the result of `scc` has no cycles Nov 30, 2018

@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Nov 30, 2018

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

This comment has been minimized.

Copy link
Author

michaelpj commented Nov 30, 2018

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

@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Nov 30, 2018

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

This comment has been minimized.

Copy link
Author

michaelpj commented Nov 30, 2018

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

@subttle

This comment has been minimized.

Copy link
Contributor

subttle commented Dec 16, 2018

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

@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Dec 16, 2018

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

@subttle

This comment has been minimized.

Copy link
Contributor

subttle commented Dec 16, 2018

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

This comment has been minimized.

Copy link

chessai commented Jan 12, 2019

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

@snowleopard

This comment has been minimized.

Copy link
Owner

snowleopard commented Jan 12, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment