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

Ivan Lazar Miljenovic ivan.miljenovic at
Tue Apr 3 00:54:11 UTC 2018

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

More information about the Libraries mailing list