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

[Olivier S.]

2018-04-03 9:50 GMT+02:00 Ivan Lazar Miljenovic <ivan.miljenovic at gmail.com>:

>
>
> On Tue, 3 Apr. 2018, 5:31 pm Olivier S., <olivier.sohn at gmail.com> 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 at gmail.com>:
>>
>>> 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
>>>
>>
>> --
>
> Ivan Miljenovic
> On mobile; please excuse any tpyos
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20180403/bceeb6b8/attachment-0001.html>