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