On Mon, 10 May 2010, Ivan Lazar Miljenovic wrote:
As I said, we're considering using an Associated Type to let users choose what type they want to use (probably with a default Map instance for this). However, we'd recommend/push the Int-based one.
I do not see why there is the need for any type extension, at all. Consider cabal-sort, a very basic program, that is Haskell-98 today, will no longer run in Hugs and JHC (untested so far) because it uses FGL's topological sort when FGL upgraded to associated types.
Well, if we let the vertex type be _anything_ (that is an instance of Ord; we'll probably require that much at least, though maybe just Eq would make sense for list-based graphs), then how do we generate newNodes? Require Enum? Bounded?
You might consider a new type class. I argued in the past, that using Ord as type class for Set and Map was not the best choice, but in order to stay consistent with the 'containers' package you may define a sub-class of Ord as class for node types.
Really, performance aside, this is my biggest possible problem with generic label types is that it may make it harder to define various algorithms on graphs because you can no longer guarantee what you can do with the vertex types; as such people may resort to requring the vertex type to be Int or something to use a specific algorithm.
Interesting, what graph algorithms rely on nodes being represented by Ints? Matrix based graph algorithms? But they have to compress the actual set of Node values in a graph to a sequence 0..n, too.