Henning Thielemann
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.
How should it be able to specify a fixed type value for the vertex type? We can't specify that g :: * -> * -> * -> * because the vertex type should _not_ be a parameter in that sense (since for many graphs it won't be, and we need some way of specifying what it is). And, to be honest, I don't really care about Hugs (JHC I do in the sense that it sounds cool but I haven't even downloaded the source yet let alone tried it).
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.
Huh? What's wrong with Ord? The only reason I said maybe Eq is in case someone stupidly decided to make [(a, [a])] a graph.
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.
None require Ints per-se; it's knowing what you _can_ do with the vertices that could be a problem. For example, I've used [1..] a few times when dealing with vertices; what should I replace that with? "enumFrom minBound" (thus requiring the vertex type to be an instance of Bounded and Enum)? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com