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

[Ivan Lazar Miljenovic]

On 3 April 2018 at 10:11, Olivier S. <olivier.sohn at gmail.com> wrote:
>
>
> 2018-04-03 1:51 GMT+02:00 Ivan Lazar Miljenovic <ivan.miljenovic at gmail.com>:
>>
>> On 3 April 2018 at 09:24, Olivier S. <olivier.sohn at gmail.com> 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 at gmail.com
http://IvanMiljenovic.wordpress.com