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

[Heinrich Apfelmus]

Ivan Lazar Miljenovic wrote:
> Heinrich Apfelmus writes:
>>
>> Graphs with different node types don't behave differently; graphs are
>> parametric with respect to the node type, just like lists don't behave
>> differently on different element types.
> 
> There will be a Map-based graph available that will have the node type
> parameter, but the variant that's currently called PatriciaTree will
> most likely be the preferred default one (as it will have better
> performance due to its use of IntMap).
> 
> We can't require the class to have the vertex type as a type parameter
> for when we want a graph (such as PatriciaTree) _with_ a fixed vertex
> type.

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.


> Actually, I've looked through my code and it appears that (apart from
> verboseness), there won't be too much of a problem with removing the
> assumption of vertex type == Int.
> 
> 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.

>> Other than that, I don't see much of a difference between custom vertex
>> types and  Int  . Internally, you can always use  Int  to reference
>> nodes and keep the association between the custom vertex type and  Int
>> in a separate map, like this
>>
>>    data Graph node a b =
>>        Graph { internal :: Gr a b , nodes :: Map node a }
> 
> Custom vertex types will work; it's just that using Int will probably
> prove to be in general more efficient and easier to use.  I haven't said
> we'll disallow custom vertex types, but I don't plan on going on the
> extreme of having optional labels, or of making the vertex type a type
> parameter for all graphs (since as I've said, you don't/can't always
> want/assume that).

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.



Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com