Duplicate information of node label

[patrickdoc]

Duplicate information of node label

[patrickdoc]

My only worry is ending up in a position where you have a Context but not the node itself. matchAny was going to be my example, but I see that you handled that case. It is probably possible to enforce that if the user has a context they also have the node label, but I haven't given much thought to it.
(Also, it is a minor issue but ctx & g becomes l & ctx g which is not quite as nice looking.)

So, short answer: I'm open to removing it if I can be reasonably certain the user won't get into a bad position. And I'm already mostly convinced.

Long answer:

In truth, heads and tails are also duplicated and somewhat unnecessary. Storing both ends of a directed edge doubles the space complexity, but makes reversal effectively O(1) with a newtype wrapper. There are definitely cases where you want this, but also some where you don't. At the moment, the user is forced to accept my trade-offs, which I don't think is a great situation.

On the denot branch I am trying something a little different. People use graphs in very different ways, so I am looking to make a more general graph representation. I've been modelling graphs as a function node -> node -> edge, which seems to be working reasonably well so far. It is interesting to note how similar this is to (node,node) -> edge (adjacency matrix) or node -> (node -> edge) (~adjacency list).

I think the hashing-based representation is a pretty good general-use graph, so I do want to port it over. But I also want to give the user some ability to make their own. For example, if their keys are Int's, they should be able to use Data.IntMap or the strict variant directly. Another interesting solution would be to make Context' the node type of the graph, and then just hash it using the self label.

Sorry for the long post, I've just been trying to nail down a solid general core graph definition and keep finding new ways people want to use graphs.

[nobrakal]

I don't know how an user can have a Context' without a node, because the only way to obtain is a Context' is the HashMap, and thus through node (Not for matchAny, but the function definition can be extended to return the node label)). A Context' alone has not many sense anyway...

ctx & g becomes l & ctx g which is not quite as nice looking

Yep, must think a bout a clean syntax (&)... A not-beautiful-but-working solution is defining a real Context as (b,Context' a b)

Short response:
I think trying this with algorithm implementation will certainly reveal if this was a good idea ^^

Long response:

• About the choices made for the implementation: I think the hashing-based is a great point of view, and efficient, view for a fgl implementation. Definitely need specialized modules with Data.IntMap, between I am not sure on how to do that without duplicate too many code ^^.
  Using a hash of the self may be a good idea, but it feels like a duplication, since the label can be the key itself.

• About the denot branch: I didn't saw that, that is a pretty way of thinking about graphs :D

[nobrakal]

Here is a version with fully removed self record: nobrakal@46933c6
I used almost systematically the type (b,Context' a b), it may be a good idea to pose type Context a b = (b, Context' a b).

Tests are passing :)

[patrickdoc]

Looks good! You can go ahead and define type Context a b = (b, Context' a b) and make a PR. Thanks!

[patrickdoc]

Closed by #13