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

On 11 May 2010 00:16, Henning Thielemann wrote:

On Tue, 11 May 2010, Ivan Lazar Miljenovic wrote:

...

Henning Thielemann writes:

...

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

If I understand you right, you say that explicit type parameters for labels are ok, because I can set them to () if not needed, but for an alternative node type you find an explicit type parameter inappropriate?

An explicit type parameter for the vertex type is not appropriate for this reason: you don't want to change it. If we had that g :: * -> * -> * -> *, then you'd have to explicitly carry around your vertex type with you everywhere for all functions with the hint that it might be possible to change (like the label types are). Now, when using a generic Map-based graph representation, this is unavoidable; but when using a custom type with a given fixed vertex type, it should be implicit what that vertex type is without having to carry it around and specify it in the type signature. By specifying it as an Associated Type when defining the instance, that type is accessible to functions that need it and can be ignored for those that don't. For labels, however, we _have_ to have them as type parameters to be able to have mapping functions (how else do you indicate that the type of the labels has changed?). What you seem to want is an explicit hierarchy of graphs where labels are an "extra". There are two (feasible) options that I see to this: 1) My so-far-mainly-vapourware generic graph class (see http://code.haskell.org/~ivanm/Graph.hs for a draft) has a base graph class that specifies what the label types are as ATs but allows you to fix them when defining an instance (you still need to set that the label type is (), but there will be convenience functions for use for labels of that type). This has the added advantage of you being able to treat Cabal's PackageIndex type as a graph in its own right (as it is). Currently we're taking a few ideas from this for FGL, but FGL will probably always require the double-label kind that it currently has (with the idea being that FGL is a "nice" wrapper around the set of classes). The main problem with this at the moment is that there's no real way to bridge the gap: the current type checker doesn't allow equality constraints in superclass contexts (so there's no way of stating that the VLabel type of a graph corresponds to its first type parameter, etc.). 2) Edward Kmett has some interesting notions in terms of _annotated_ graphs. I'm not sure if I follow exactly how it will work, but from what I understand it might be possible to add labels to a graph as an annotated extension. Whichever way ends up getting implemented and chosen, it will not affect FGL: its graphs will always require two type parameters for the labels (however, you _will_ be able to create a new instance which forces those labels to always be () if you so wish). -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com