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

[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.

> 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.