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

2018-04-03 9:50 GMT+02:00 Ivan Lazar Miljenovic :

On Tue, 3 Apr. 2018, 5:31 pm Olivier S., wrote:

...

I think in your example, nodes are `()` by the current meaning of node in graphFromEdges.

To be closer to what graphFromEdges does today, we should change it to:

`data MyNode key nodeData = MyNode nodeData key [key]`

No, `node ~ MyNode` in my example. Whilst the key may be the unique identifier, the node type itself may be richer (and contain the key!).

Just wanted to point out that if the node contains some data which is neither key not list of neighbours, then `Map key [key]` won't be enough.

...

2018-04-03 2:54 GMT+02:00 Ivan Lazar Miljenovic < ivan.miljenovic@gmail.com>:

...

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

...

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

ivan.miljenovic@gmail.com>:

...

...

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

--

Ivan Miljenovic On mobile; please excuse any tpyos