Re: Proposal for Data.Graph : Improve graph creation complexity when nodes have "consecutive" keys

On 3 April 2018 at 10:11, Olivier S. wrote:

2018-04-03 1:51 GMT+02:00 Ivan Lazar Miljenovic :

...

On 3 April 2018 at 09:24, Olivier S. wrote:

...

So it seems using Data.IntMap would be a good compromise?

IntMap only works if `node ~ Int`; otherwise we lose generality.

I was under the impression that we can replace [(node, key, [key])], by IntMap (node, [Int]), node being anything we want. Is it not true?

I've never used Data.Graph in anger, but my understanding is that in the most polymorphic sense you may consider the equivalent of `Map node [key]` along with a `node -> key` function. For example: `data MyNode key = MyNode { nodeID :: key, edges :: [key]}`; then you could have `graphFromEdges . map (\mn -> (mn, nodeID mn, edges mn))`. At this point in time the actual type of `node` is no longer useful, so having `graphFromEdges` consume a `Map key [key]` may suffice... but then you can't get back the original node type to map back to your original values. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com http://IvanMiljenovic.wordpress.com