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

[Ivan Lazar Miljenovic]

Henning Thielemann <lemming at henning-thielemann.de> writes:

> 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 at gmail.com
IvanMiljenovic.wordpress.com