-
Notifications
You must be signed in to change notification settings - Fork 68
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
Idea: Add SubGraph data type #61
Comments
Interesting. I haven't though about exactly your version of data Graph a where
Empty :: Graph a
Vertex :: a -> Graph a
Overlay :: Graph a -> Graph a -> Graph a
Connect :: Graph a -> Graph a -> Graph a
Fmap :: (a -> b) -> Graph a -> Graph b
Bind :: (a -> Graph b) -> Graph a -> Graph b
... This also allows some efficient algorithms. My initial impression is that your I'd like to explore this direction.
I think we could simply have a strict version of this type, e.g.
Can you give a specific example?
Yes, that would be great! |
Absolutely, but why should they be in
That is true, but the algorithm doesn't need to consider all constructors, just call
Sounds good!
Only trivial examples so far where we could get constant instead of linear time; |
Right, I see what you mean. Perhaps, this could indeed be useful, but I also can't come up with convincing examples. The
Let's keep this issue open. Perhaps, we'll come up with a good use for the |
@nobrakal Thanks! I didn't really explain what I meant by experiments: I meant to measure performance of graph consumption algorithms: if they take longer, it means some extra work was needed. So you should pick the |
@snowleopard Oops, sorry for this, I copied/pasted my comment is the wrong issue, I just deleted it (here it was totally without sense :p ) and moved to the right issue ! |
The idea is to decouple the graph creation functions from the actual graph creation. In code:
This should have the same performance characteristics as the current implementation, since it is just laziness made explicit. It is also very similar to the
Cached
data type in #19. There could be the following benefits:Graph
data type could be made strict. I am not sure if it is a good idea, but it would be possible without too much of a performance hit.A reason not to do it is that it is so far unclear, which algorithms actually benefit from such a structure. Since the
SubGraph
is not necessarily a module, it is not clear whether a algorithm could take advantage of it.Ultimately the usefulness of this proposal depends a lot on the subgraphs and algorithms. Do you have some ideas @snowleopard? I have so far experimented with Hanoi and Turan graphs, but I have not found anything useful.
The text was updated successfully, but these errors were encountered: