[Haskell-cafe] Re: What do _you_ want to see in FGL?

[Ivan Miljenovic]

On 13 May 2010 17:09, Heinrich Apfelmus <apfelmus at quantentunnel.de> wrote:
> Ah, ok, you want graphs that only work with one node type. If there is
> at most one such graph for each node type, you could make a data type
> family and retain the parameter, though
>
>    data family Graph node :: * -> *
>    data family Graph Int  a b = PatriciaTree a b
>    data family Graph node a b = GenericTree
>
> But it seems that this doesn't work because the cases overlap.

Yup: PatriciaTree, VectorGraph, etc.

>> However, I can't see any reason why someone would only want to use even
>> Int values.  As I think I've said before (I've been making these
>> arguments in various threads and discussions, so I'm not sure if I've
>> said it here): the vertex type is just an _index_ to ensure consistency,
>> etc; it is _not_ IMHO meant to represent the actual data: that's what
>> the labels are for.
>
> Yes, the integers are just indexes. Of course, the example with the even
> integers is a bit silly; but if the integers are actually indexes, then
> it's conceptually cleaner to make them abstract, i.e.
>
>    data Node  -- constructors are not exported
>
> and provide combinators to operate on these abstract indexes, including
> a corresponding Data.Graph.Inductive.NodeMap module.
>
> I'd like to see such an abstract  Node  type, because then the library
> will provide all operations I need. It took me some time to figure out
> how to best use  Int  as indexes in my example code; an abstract  Node
> type and a good  NodeMap  module would have made my life much easier.

I'm not sure I understand what you're saying here: first you said you
wanted to be able to specify a vertex type, now you're saying that you
don't want to know what the vertex type even is (except that it's some
abstract Node type)?  Whilst this would make graph usage safer/more
robust, this seems to contradict your earlier arguments...

> Darn, I meant
>
>    data Graph node a b =
>        Graph { internal :: Graph Int a b, nodes :: Map Int a }
>
> The idea is to use  Ints  internally and only store a loose association
> to the custom vertex type. In particular, no  Map a Int  is required,
> only from  Int  to  a . Now, I realize that the other way round is
> required as well for querying the context of a node in a graph.

What's the point of that useless node type parameter then?  And how
does the nodes map differ from just getting the graph label?

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com