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

[Ivan Miljenovic]

On 11 May 2010 00:16, Henning Thielemann <lemming at henning-thielemann.de> wrote:
>
> On Tue, 11 May 2010, Ivan Lazar Miljenovic wrote:
>
>> Henning Thielemann <lemming at henning-thielemann.de> 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 at gmail.com
IvanMiljenovic.wordpress.com